#include <iostream>
#include<fstream>
#include<vector>
#include<queue>
using namespace std;
#define MAX 2147483647
int n,m,v[50001],i,x,y,z,j,k,e,w,/*l[50001],*/nr,A,B;
bool t[50001],ok;
struct nod
{
    int x,c;
}q;
vector < nod > a[50001];
int h[250001],H,S[250001],F[250001],C[250001];
void up(int &i)
{
    while(i/2>0&&C[h[i]]<C[h[i/2]])
    {
        swap(h[i],h[i/2]);
        i/=2;
    }
}
void down(int &i)
{
    A=2*i;B=2*i+1;++H;
    ok=0;
    while(ok<1)
    {
        if(B<H)
        {
            if(C[h[B]]<C[h[A]])
            {
                if(C[h[i]]>C[h[B]])
                {
                    swap(h[B],h[i]);
                    i=B;A=2*i;B=A+1;
                }
                else
                    ok=1;
            }
            else
            {
                if(C[h[i]]>C[h[A]])
                {
                    swap(h[A],h[i]);
                    i=A;A=2*i;B=A+1;
                }
            }
        }
        else
        {
            if(A<H)
            {
                if(C[h[i]]>C[h[A]])
                {
                    swap(h[A],h[i]);
                    i=A;ok=1;
                }
                else ok=1;
            }
            else ok=1;
        }
    }
    --H;
}
void el()
{
    if(H>2)
    {
        swap(h[1],h[H]);
        --H;
        x=1;
        down(x);
    }
    else
        {
            if(H>1)
            {
                h[1]=h[2];--H;
            }
            else
                h[1]=0;
        }
}
int main()
{
    ifstream f("dijkstra.in");
    f>>n>>m;
    for(i=0;i<m;++i)
    {
        f>>x>>q.x>>q.c;
        /*if(x<q.x)*/a[x].push_back(q);//++l[x];
    }
    f.close();
    ++n;
    for(i=2;i<n;++i){v[i]=MAX;t[i]=0;}
    //--n;
    //FA PARCURGERE,NU LUA NODURILE DUPA NUMAR!!!!
 //   coada.push(1);//t[1]=1;
    k=a[1].size();
    for(i=0;i<k;++i)
    {
        h[++H]=i+1;
        S[i+1]=1;
        F[i+1]=a[1][i].x;
        C[i+1]=a[1][i].c;
        j=H;
        up(j);
    }
    nr=k;
    //for(i=1;i<=H;++i)cout<<h[i]<<" ";cout<<'\n';
    while(h[1]>0)
    {
        i=S[h[1]];
        y=h[1];t[i]=1;//coada.pop();
        //cout<<i<<":";
        el();
        //for(i=1;i<=H;++i)cout<<h[i]<<" ";cout<<'\n';
        //k=a[i].size();//l[i];//cout<<k<<" ";
/*        for(j=0;j<k;++j)
        {*/
            e=C[y]+v[i];
            w=F[y];
            //xx=a[i][j].x;qq=a[i][j].c;
            if(e<v[w])
            {
                v[w]=e;//a[i][j].c+v[i];
            }
            //cout<<w<<" "<<t[w]<<'\n';
            if(t[w]<1)
            {
                k=a[w].size();
                for(i=0;i<k;++i)
                {
                    ++nr;
                    h[++H]=nr;
                    S[nr]=w;F[nr]=a[w][i].x;C[nr]=a[w][i].c;
                    x=H;up(x);
                }
            }
        //*/

        //cout<<nr<<" ";
    }
    ofstream g("dijkstra.out");
    //++n;
    x=MAX-1;
    for(i=2;i<n;++i)
        if(x<v[i])g<<"0 ";
        else g<<v[i]<<" ";
    return 0;
}