#include<cstdio>
#include<vector>
#include<iterator>
#include<utility>
#include<queue>
#define NMAX 50000+5
#define oo 1<<30
using namespace std;
int N,M,a,b,c,i,j;
int D[NMAX];
vector<pair<int,int> > V[NMAX];
vector<pair<int,int> >::iterator it;
priority_queue<pair<int,int> > 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",&a,&b,&c);
        V[a].push_back(make_pair(b,c));
    }
    for(i=2;i<=N;i++) D[i]=oo;
    Q.push(make_pair(1,0));
    for(;!Q.empty();)
    {
        a=Q.top().first;
        Q.pop();
        for(it=V[a].begin();it!=V[a].end();it++)
        {
            if(D[a]+it->second<D[it->first])
            {
                D[it->first]=D[a]+it->second;
                Q.push(make_pair(it->first,D[it->first]));
            }
        }
    }
    for(i=2;i<=N;i++) printf("%d ",D[i]);
    return 0;
}