#include <iostream>
#include<fstream>
#include<vector>
using namespace std;
#define MAX 214748364
int n,m,p[50001],v[50001],h[50001],i,j,H,c,x,y,k;
//bool t[50001];
bool ok;
struct nod
{
    int x,c;
}q;
vector < nod > a[50001];
void up(int j)
{
    while(j/2>0&&v[h[j]]<v[h[j/2]])
    {
        swap(h[j],h[j/2]);
        p[h[j]]=j;p[h[j/2]]=j/2;
        j/=2;
    }
}
void down(int j)
{
    ok=0;
    while(ok<1)
    {
        if(2*j<H)
        {
            if(v[h[2*j+1]]<v[h[2*j]])
            {
                if(v[h[j]]>v[h[2*j+1]])
                {
                    swap(h[j],h[2*j+1]);
                    p[j]=j;p[2*j+1]=2*j+1;
                    j=j*2+1;
                }
                else ok=1;
            }
            else
            {
                if(v[h[j]]>v[h[2*j]])
                {
                    swap(h[j],h[2*j]);
                    p[j]=j;p[2*j]=2*j;
                    j=j*2;
                }
                else ok=1;
            }
        }
        else
        {
            if(2*j-1<H)
            {
                if(v[h[j]]>v[h[2*j]])
                {
                    swap(h[j],h[2*j]);
                    p[j]=j;p[2*j]=2*j;
                    j=j*2;
                }
                else ok=1;
            }
            else ok=1;
        }
    }
}
void el()
{
    if(H>2)
    {
        swap(h[1],h[H]);p[h[1]]=1;p[h[H]]=H;--H;
        down(1);
    }
    else
    {
        if(H>1)
        {
            swap(h[1],h[H]);p[h[1]]=1;--H;
        }
        else
        {
            h[1]=0;--H;
        }
    }
}
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;h[i]=i;p[i]=i;}
    h[1]=1;p[1]=1;H=n-1;
    //--n;
    //FA PARCURGERE,NU LUA NODURILE DUPA NUMAR!!!!
    //t[1]=1;
    while(h[1]>0)
    {
        i=h[1];c=v[i];el();
        k=a[i].size();
        for(j=0;j<k;++j)
        {
            x=a[i][j].x;y=a[i][j].c;
            if(v[i]+y<v[x])
            {
                v[x]=v[i]+y;up(p[x]);
            }
        }
    }
    ofstream g("dijkstra.out");
    //++n;
    for(i=2;i<n;++i)
        if(v[i]<MAX)g<<v[i]<<" ";
        else g<<"0 ";
    return 0;
}