#include <bits/stdc++.h>
using namespace std;
const int nmax=5e4+5;
const int inf=1e9;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
int d[nmax];
int v[nmax];
int n;
vector<pair<int,int>>adj[nmax];
void dijk(int s)
{
    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>heap;
    heap.push({0,s});
    while(!heap.empty())
    {
        int nod = heap.top().second;
        heap.pop();
        if(!v[nod])
        for(auto it: adj[nod])
                if(d[nod]+it.second<d[it.first])
                {
                    d[it.first]=d[nod]+it.second;
                    heap.push({d[it.first],it.first});
                }
        v[nod]=1;
    }
    for(int i=2;i<=n;i++)
    if(d[i]==inf)
    g<<0<<' ';
    else
        g<<d[i]<<' ';
}


int main()
{ int m;
    f>>n>>m;
    for(int i=2;i<=n;i++)
        d[i]=inf;
    while(m--)
    {
        int x,y,c;
        f>>x>>y>>c;
        adj[x].push_back({y,c});
    }
    dijk(1);

        

}