#include <bits/stdc++.h>
using namespace std;

#define INF 99999999
queue <int> q;
vector <int> G[50100],C[50100];


int d[50100],x,y,c,m,n;


int main()
{
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);

    scanf("%d%d",&n,&m);
    for(int i=2;i<=n;i++)
        d[i]=INF;

    while(m--){
        scanf("%d%d%d",&x,&y,&c);
        G[x].push_back(y);
        C[x].push_back(c);

    }

    q.push(1);

    while(!q.empty()){
        x = q.front();
        for(int i=0;i<G[x].size();i++)
            if(d[G[x][i]] > d[x] + C[x][i])
        {
            d[G[x][i]] = d[x] + C[x][i];
            q.push(G[x][i]);
        }
        q.pop();
    }

    for(int i=2;i<=n;i++)
                if(d[i]==INF) printf("%d ",0);
                else printf("%d ",d[i]);
                return 0;

}