#include <fstream>
#include<climits>
using namespace std;
ifstream cin ("dijkstra.in");
ofstream cout ("dijkstra.out");
int t[3][250001],n,m,start[50001],d[50001],v[50001],l;
void read ()
{ int k=0,a,b,c;
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>a>>b>>c;
        t[0][++k]=b; t[1][k]=start[a]; start[a]=k; t[2][k]=c;
    }
}
void init ()
{
    for(int i=1;i<=n;i++) d[i]=INT_MAX;
}
void down (int poz)
{
    int val=v[poz],fiu;
    while(3>2)
    { fiu=0;
        if(poz*2<=l) fiu=poz*2;
        if(poz*2+1<=l && d[v[poz*2+1]]>d[v[fiu]]) fiu=2*poz+1;
        if(d[val]>d[v[fiu]] && fiu!=0)
                v[poz]=v[fiu],poz=fiu;
                else { v[poz]=val; break; }
    }
}
void climb (int poz)
{
    int val=v[poz];
    while(3>2)
    {
        if(d[v[poz/2]]>d[val])
            v[poz]=v[poz/2],poz/=2;
            else { v[poz]=val; break; }
    }
}
void dijkstra ()
{
    v[1]=1; d[1]=0; l=1;
    for(int i=1;i<=n;i++)
    {
        int poz=v[1];  v[1]=v[l]; l--; down(1);
        int x=start[poz];
        while(x)
        {
            if(d[t[0][x]]>d[poz]+t[2][x])
            {
                d[t[0][x]]=d[poz]+t[2][x]; v[++l]=t[0][x]; climb(l);
            } x=t[1][x];
        }
    }
}
void write ()
{
    for(int i=2;i<=n;i++) {if(d[i]==INT_MAX) d[i]=0; cout<<d[i]<<" ";}
}
int main()
{
    read();
    init();
    dijkstra();
    write();
    cin.close();
    cout.close();
    return 0;
}