#include <fstream>
# define nmax 50002
# define mmax 250002
# define inf 2000000000

using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

int n,m;
int x,y,c;
struct muchie
{
    int x,y,c;
};
muchie G[mmax];
int D[nmax];

int main ()
{
    int ok=0,i;
    f>>n>>m;
    for(i=1;i<=m;++i)
    {
        f>>G[i].x>>G[i].y>>G[i].c;
        if(x==1) D[y]=1;
    }
    for (i=2;i<=n;++i)
        if (D[i] == 0) D[i]=inf;

    while(ok==0)
    {
        ok=1;
        for(i=1;i<=m;i++)
            if (D[G[i].y] > D[G[i].x] + G[i].c)
            {
                D[G[i].y] = D[G[i].x] + G[i].c;
                ok=0;
           }
    }
    for(i=2;i<=n;++i)
    {
        if(D[i]!=inf ) g<<D[i]<<' ';
           else g<<0<<' ';
    }

    return 0;
}