#include<cstdio>
#include<vector>
#include<queue>
#define inf 999999
#define maxn 50001
using namespace std;
vector <int > G[maxn],C[maxn];
queue <pair <int,int> > Q;
int n,m,d[maxn],x,y,c;
void D(){
    for(int i=2;i<=n;++i)
        d[i]=inf;
    d[1]=0;
    Q.push(make_pair(0,1)); //0-cost 1-nod
    while(!Q.empty()){
        pair <int,int> A;
        A=Q.front(); Q.pop();
         int val=A.first;
        int nod=A.second;
        for(int i=0;i<G[nod].size();++i){
                int p=G[nod][i];
            if(d[p]>C[nod][i]+val){
                d[p]=C[nod][i]+val;
                Q.push(make_pair(d[p],p));
            }
        }
    }
}
int main(){
        freopen("dijkstra.in","r",stdin);
        freopen("dijkstra.out","w",stdout);
        scanf("%d%d",&n,&m);
        for(int i=1;i<=m;++i){
            scanf("%d%d%d",&x,&y,&c);
            G[x].push_back(y);
            C[x].push_back(c);
        }
        D();
        for(int i=2;i<=n;++i)
            if(d[i]==inf)
                printf("%d ",0);
            else
                printf("%d ",d[i]);
        return 0;
}