#include<iostream>
#include<vector>
#include<fstream>
using namespace std;
#define MAX 2147483647
struct nod
{
    int x,c;
}q;
vector<nod>a[50001];
nod h[50001];
int x,y,z,n,m,i,j,e,w,A,B,H,k,v[50001],p[50001],u;
bool ok;
inline void up(int &i)
{
    while(i/2>0&&h[i].c<h[i/2].c)
    {
        //swap()
        swap(h[i],h[i/2]);
        p[h[i/2].x]=i/2;
        p[h[i].x]=i;
        i/=2;
    }
}
inline void down(int &i)
{
    A=2*i;B=2*i+1;++H;
    ok=0;
    while(ok<1)
    {
        if(B<H)
        {
            if(h[B].c<h[A].c)
            {
                if(h[i].c>h[B].c)
                {
                    swap(h[B],h[i]);//p[h[i].x]=i;
                    p[h[B].x]=B;
                    p[h[i].x]=i;
                    i=B;A=2*i;B=A+1;
                }
                else
                    ok=1;
            }
            else
            {
                if(h[i].c>h[A].c)
                {
                    swap(h[A],h[i]);
                    p[h[A].x]=A;
                    p[h[i].x]=i;
                    i=A;A=2*i;B=A+1;
                }
            }
        }
        else
        {
            if(A<H)
            {
                if(h[i].c>h[A].c)
                {
                    swap(h[A],h[i]);
                    p[h[A].x]=A;
                    p[h[i].x]=i;
                    i=A;ok=1;
                }
                else ok=1;
            }
            else ok=1;
        }
    }
    --H;
}
void el()
{
    if(H>2)
    {
        swap(h[1],h[H]);
        p[h[1].x]=1;
        p[h[H].x]=H;
        --H;
        x=1;
        down(x);
    }
    else
        {
            if(H>1)
            {
                h[1]=h[2];--H;
            }
            else
                h[1].x=0;
        }
}
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();
    for(i=2;i<n;++i)v[i]=MAX;
    h[1].c=0;h[1].x=1;v[1]=0;
    while(h[1].x<1)
    {
        i=h[1].x;
        x=h[1].c;
        k=a[i].size();
        el();
        for(j=0;j<k;++j)
        {
            if(p[a[i][j].x]<1)
            {
                h[++H].x=a[i][j].x;
                p[a[i][j].x]=H;
                h[H].c=a[i][j].c+x;
                v[h[H].x]=h[H].c;
                j=H;
                up(j);
            }
            else
            {
                u=p[a[i][j].x];
                if(h[u].c>x+a[i][j].c)
                {
                    v[a[i][j].x]=x+a[i][j].c;
                    h[u].c=x+a[i][j].c;
                }
            }
        }
    }
    ofstream g("dijkstra.out");
    for(i=2;i<n;++i)
        g<<v[i]<<" ";
    return 0;
}