#include <iostream>
#include<fstream>
#include<vector>
using namespace std;
#define MAX 1073741824
struct nod
{
    int x,c;
}q;
bool ok;
int n,m,v[50001],h[50001],p[50001],i,j,x,H,y,z,k;
vector<nod>a[250001];
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(j*2<H)
        {
            if(v[h[j*2]]<v[h[j*2+1]])
            {
                if(v[h[j*2]]<v[h[j]])
                {
                    swap(h[j*2],h[j]);
                    p[h[j*2]]=j*2;
                    p[h[j]]=j;
                    j*=2;
                }
                else ok=1;
            }
            else
            {
                if(v[h[j*2+1]]<v[h[j]])
                {
                    swap(h[j*2+1],h[j]);
                    p[h[j*2+1]]=j*2+1;
                    p[h[j]]=j;
                    j=j*2+1;
                }
                else ok=1;
            }
        }
        else
        {
            if(j*2-1<H)
            {
                if(v[h[j*2]]<v[h[j]])
                {
                    swap(h[j*2],h[j]);
                    p[h[j]]=j;p[h[j*2]]=j*2;
                    ok=1;
                }
                else ok=1;
            }
            else ok=1;
        }
    }
}
void el()
{
    if(H>2)
    {
        swap(h[H],h[1]);p[h[H]]=H;p[h[1]]=1;
        --H;
        down(1);
    }
    else
    {
        if(H>1)
        {
            swap(h[1],h[2]);p[h[1]]=1;p[h[2]]=2;
            --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;
        a[x].push_back(q);
    }
    f.close();
    H=n;
    ++n;
    for(i=2;i<n;++i)
    {
        p[i]=i;
        h[i]=i;
        v[i]=MAX;
    }
    h[1]=1;p[1]=1;v[1]=0;
    while(h[1]>0)
    {
        i=h[1];x=v[i];
        //el();
        k=a[i].size();
        for(j=0;j<k;++j)
        {
            y=a[i][j].x;z=a[i][j].c;
            if(x+z<v[y])
            {
                v[y]=x+z;
                up(p[y]);
            }
        }
        el();
    }
    ofstream g("dijkstra.out");
    for(i=2;i<n;++i)
        if(v[i]<MAX)g<<v[i]<<" ";
        else g<<"0 ";
    g.close();
   /* ifstream f1("dijkstra.out");
    ifstream f2("asd.out");
    f1>>x;f2>>y;
    i=2;
    while(!f2.eof())
    {
        if(x!=y)cout<<i<<" "<<x<<" "<<y<<'\n';
        f1>>x;f2>>y;
        ++i;
    }*/
    return 0;
}