#include <stdio.h>   
#include <algorithm>   
#include <queue>   
#include <vector>   
#include <bitset>   
using namespace std;   
#define NMAX 65536   
#define INF 0x3f3f3f3f   
#define pb(a) push_back(a)   
vector<long> veci[NMAX],cost[NMAX];   
long n,m,a,b,c,i,d[NMAX],nod;    
int main()   
{   
    freopen ("dijkstra.in","r",stdin);   
    freopen ("dijkstra.out","w",stdout);   
    scanf("%ld %ld",&n,&m);   
    for (i=1;i<m+1;++i){   
        scanf("%ld %ld %ld",&a,&b,&c);   
        veci[a].pb(b);   
        cost[a].pb(c);   
        }   
    //---------------------------   
    bitset <NMAX> iq;   
    queue<long> q;   
    memset(d, INF, sizeof(d));   
       
    d[1]=0;   
    q.push(1);   
    iq[1]=1;   
       
    while (!q.empty()){   
          nod=q.front();   
          q.pop();   
          iq[nod]=0;   
          for (i=0;i<veci[nod].size();++i)   
              if (d[nod]+cost[nod][i]<d[veci[nod][i]]){   
                 d[veci[nod][i]]= d[nod] +cost[nod][i];   
                 if (!iq[veci[nod][i]]){   
                    q.push(veci[nod][i]);   
                    iq[veci[nod][i]]=1;   
                    }   
                 }   
          }   
    //-----------------------------------   
    for (i=2;i<n+1;++i)   
        if (d[i]<INF)printf("%ld ",d[i]);
        else printf("0 ");
    
    return 0;   
}