#include <cstdio>
#include <algorithm>
#include <vector>
#define INF (1<<31) -1
#define NMAX 50005
 
using namespace std;
 
struct node
{
    int x,cost;
};
node pp(int a,int b)
{
    node X;X.x=a;X.cost=b;
    return X;
}
vector<node>v[NMAX];
int n,m,lg;
int Poz[NMAX],H[NMAX*2],d[NMAX];
 void urcaheap(int poz){
    while(poz > 1 && d[H[poz]] < d[H[poz/2]]){
        swap(H[poz],H[poz/2]);
        swap(Poz[H[poz]],Poz[H[poz/2]]);
        poz=poz/2;
    }
}
void bagaheap(int x)
{
        ++lg;
        H[lg]=x;
        Poz[x]=lg;
        urcaheap(lg);
}
 
void coboara(int poz)
{
    while((poz * 2 <=lg && d[H[poz]] > d[H[poz*2]]) || (poz*2+1<=lg+1 && d[H[poz]] > d[H[poz*2+1]])){
        if(poz*2 + 1 > lg || d[H[poz*2]] < d[H[poz*2+1]]){
            swap(H[poz*2],H[poz]);
            swap(Poz[H[poz*2]],Poz[H[poz]]);
            poz=poz*2;
        }
        else{
            swap(H[poz*2+1],H[poz]);
            swap(Poz[H[poz*2+1]],Poz[H[poz]]);
            poz=poz*2+1;
        }
    }
}
int Minim(){
    int M=H[1];
    Poz[M]=0;
    Poz[H[lg]]=1;
    H[1]=H[lg];
    --lg;
    coboara(1);
    return M;
}
 
 
int main()
{
    freopen("bellmanford.in","r",stdin);
    freopen("bellmanford.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;++i)
    {
        int x,y,c;
        scanf("%d%d%d",&x,&y,&c);
        v[x].push_back(pp(y,c));
    }
    for(int i=1;i<=n;++i) d[i]=INF;
    d[1]=0;
    bagaheap(1);
    while(lg > 0){
        int x=Minim();
        for(int i=0;i<v[x].size();++i)
        {
            node X=v[x][i];
            if(d[x] + X.cost < d[X.x])
            {
                d[X.x]=d[x]+X.cost;
                if(Poz[X.x] != 0) urcaheap(Poz[X.x]);
                    else bagaheap(X.x);
            }
        }
    }
 
    for(int i=2;i<=n;++i)
        if(d[i] != INF) printf("%d ",d[i]);
            else printf("0 ");
    return 0;
}