#include <bits/stdc++.h>
#define ff first
#define ss second
#define NMAX 50001
#define pb push_back
using namespace std;
const string file = "dijkstra";

ifstream fin (file+".in");
ofstream fout (file+".out");
typedef long long ll;
typedef long double ld;

const ll INF = 9223372036854775807ll;
const int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1}, inf = 2147483647;
vector < pair < int, int> > v[NMAX];
priority_queue< pair<int, int > > Q;
int d[NMAX]; bool viz[NMAX];
int N, M;
void dijkstra(int nod)
{
    Q.push({0,nod});
    viz[nod]=1;
    while(Q.size())
    {
        pair<int,int> node = Q.top();
        Q.pop();
        int nodc=node.ss;
        viz[nodc]=0;
        for (vector<pair<int,int> > :: iterator it = v[nodc].begin(); it!=v[nodc].end(); ++it)
        {
            int nodv=it->first;
            int cost=it->second;
            if(d[nodv] > d[nodc]+cost)
            {
                d[nodv]=d[nodc]+cost;
                if(!viz[nodv]) Q.push({-d[nodv],nodv}), viz[nodv]=1;
            }

        }
    }
}
int main()
{
    int x,y,c;
    fin>>N>>M;
    for(int i=1;i<=M;++i)
    {
        fin>>x>>y>>c;
        v[x].pb({y,c});
    }
    for(int i=2;i<=N;++i) d[i] = inf;
    dijkstra(1) ;
    for(int i=2;i<=N;++i) if(d[i]!=inf)fout<<d[i]<<" "; else fout<<0<<" ";
    return 0;
}