#include<cstdio>
#include<vector>
#include<queue>
#define pb push_back
#define p push
#define mp make_pair
#define PII pair<int,int>
using namespace std;
const int NMAX = 50005;
const int INF = (1<<31)-1;
int N,M,X,Y,C,Dist[NMAX],From,i;
vector<PII> V[NMAX];
priority_queue<PII,vector<PII>,greater<PII> > Q;
int main()
{
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    scanf("%d%d",&N,&M);
    for(;M;M--)
    {
        scanf("%d%d%d",&X,&Y,&C);
        V[X].pb(mp(Y,C));
    }
    for(i=2;i<=N;i++) Dist[i]=INF; Q.p(mp(0,1));
    while(!Q.empty())
    {
        From=Q.top().second; Q.pop();
        for(vector<PII>::iterator it=V[From].begin();it!=V[From].end();it++)
            if(Dist[From]+it->second<Dist[it->first])
            {
                Dist[it->first]=Dist[From]+it->second;
                Q.p(mp(Dist[it->first],it->first));
            }
    }
    for(i=2;i<=N;i++) if(Dist[i]==INF) printf("0 "); else printf("%d ",Dist[i]);
    return 0;
}