#include <cstdio>
#include<vector>
#include<queue>
#define INF 999999
#define maxn 50005
using namespace std;
FILE *f=fopen("dijkstra.in","r");
FILE *g=fopen("dijkstra.out","w");
vector <int> G[maxn],d(maxn,INF),C[maxn];
queue <pair <int,int> > Q;
int n,m,x,y,c;
void dij(){
    Q.push(make_pair(1,0)); //nod si cost
    d[1]=0;
    while(Q.empty()==0){
        pair <int,int> A=Q.front();Q.pop();
        int nod=A.first;
        int cost=A.second;
        for(int i=0;i<G[nod].size();i++)
            if(d[G[nod][i]]>cost+C[nod][i]){
                d[G[nod][i]]=cost+C[nod][i];
                Q.push(make_pair(G[nod][i],C[nod][i]));
            }
    }
}
int main()
{
    fscanf(f,"%d%d",&n,&m);
    for(int i=1;i<=m;i++){
            fscanf(f,"%d%d%d",&x,&y,&c);
        G[x].push_back(y);
        C[x].push_back(c);
    }
    dij();
    for(int i=2;i<=n;i++)
        fprintf(g,"%d ",d[i]);
    return 0;
}