#include <fstream>
#include <iostream>
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
struct el{int nod; short cost; int urm;};
el a[250001];
int n,m,cost[50001],inf=1000000000,i,j,x,y, l[50001],k=1,c,poz,mini,p;
bool viz[50001];
void ad(int x,int y,int c)
{
    k++;
    a[k].nod=y;
    a[k].cost=c;
    a[k].urm=l[x];
    l[x]=k;
}
int main()
{
    f>>n>>m;
    for(i=1;i<=n;i++)
    {
            cost[i]=inf;
    }
    cost[1]=0;
    viz[1]=1;
    for(i=1;i<=m;i++)
    {
        f>>x>>y>>c;
        ad(x,y,c);
    }
    poz=l[1];
    while(poz)
    {
        cost[a[poz].nod]=a[poz].cost;
        poz=a[poz].urm;
    }
    for(i=1;i<n;i++)
    {
        mini=inf;
        for(j=1;j<=n;j++)
            if(viz[j]==0 and cost[j]<mini)
        {
            p=j;
            mini=cost[j];
        }
        viz[p]=1;
        poz=l[p];
        while(poz)
        {
            c=a[poz].nod;
            if(cost[c]>cost[p]+a[poz].cost)
                cost[c]=cost[p]+a[poz].cost;
            poz=a[poz].urm;

        }
    }
    for(i=2;i<=n;i++)
        if(cost[i]==inf)
        g<<0<<" ";
    else
        g<<cost[i]<<" ";
    return 0;
}