using namespace std;
#include<iostream>
#include<fstream>
#include<vector>
#include<algorithm>
#define pb push_back
#define L ((i)*2)
#define R ((L)+1)
#define T ((i)/2)
#define nmax 50005
#define oo 0x3f3f3f3f
struct leg{
    int n,c;};
vector<leg> G[nmax];
int N,M,nh;
int d[nmax],H[nmax],poz[nmax];

ofstream fout("dijkstra.out");

void upheap(int i)
{
    if(i<=1) return;
    if(d[H[i]]<d[H[T]]) swap(H[i],H[T]),swap(poz[H[i]],poz[H[T]]), upheap(T);
}

void downheap(int i)
{
    int m=i;
    if(L<=nh)
     if(d[H[L]]<d[H[m]])
       m=L;
    if(R<=nh)
     if(d[H[R]]<d[H[m]])
       m=R;
    if(m!=i) swap(H[i],H[m]),swap(poz[H[i]],poz[H[m]]), downheap(m);
}

void solve()
{vector<leg>::iterator it;
int i,u;

    for(i=1;i<=N;i++)
    {
        d[i]=oo;
        H[i]=i;
        poz[i]=i;
    }
    d[1]=0;
    nh=N;

    while(nh)
    {
        u=H[1];
        swap(H[1],H[nh]);
        swap(poz[H[1]],poz[H[nh]]);
        nh--;
        downheap(poz[H[1]]);
        for(it=G[u].begin();it<G[u].end();it++)
        {
            if(d[it->n]>it->c+d[u])
             {

             d[it->n]=d[u]+it->c;
             upheap(poz[it->n]);
             }
        }



    }

    for(i=2;i<=N;i++)
    {
        if(d[i]==oo) d[i]=0;
        fout<<d[i]<<" ";
    }

}

void cit()
{int i,x,y,c;
    ifstream fin("dijkstra.in");
    fin>>N>>M;
    for(i=1;i<=M;i++)
    {

     fin>>x>>y>>c;
     G[x].pb((leg){y,c});
    }
    fin.close();
}

int main()
{
    cit();
    solve();
    fout.close();
    return 0;
}