#include<fstream>
#define dim 251001
#define dim2 51001
//#define dim 7
//#define dim2 8
#define oo 123456788
using namespace std;
int a[dim],b[dim],cost[dim],d[dim2],i,ok,m,n,minn;

int main()
{
    ifstream f("dijkstra.in");
    ofstream g("dijkstra.out");
    f>>n>>m;
    minn=oo;
    for(i=2;i<=n;i++)
        d[i]=minn;

    for(i=1;i<=m;i++)
    {
        f>>a[i]>>b[i]>>cost[i];
        if(a[i]==1)
            d[b[i]]=cost[i];
    }

    ok=0;
//5 6
//1 2 1
//1 4 2
//4 3 4
//2 3 2
//4 5 3
//3 5 6
    while(!ok)
    {
        ok=1;
        for(i=1;i<=m;i++)
            if(d[b[i]]>d[a[i]]+cost[i])
            {
                d[b[i]]=d[a[i]]+cost[i];
                ok=0;
            }
    }

    for(i=2;i<=n;i++)
        if(d[i]==minn)
            g<<"0 ";
        else
            g<<d[i]<<' ';
    return 0;
}