#include <iostream>
#include <fstream>
#define maxn 50010
#define maxm 250010
#define inf 1000000000
using namespace std;

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

struct l_muchii
{
    long x,y;
    int c;
}mm[maxm];

long i,j,n,m,cost[maxn];

void read_ini()
{
    f>>n;
    f>>m;
    for(i=1; i<=m ;i++)
    {
        f>>mm[i].x;
        f>>mm[i].y;
        f>>mm[i].c;
    }
    cost[1]=0;
    for(i=2; i<=n ;i++)
        cost[i]=inf;
}

void bellman()
{
    for(i=1; i<=n ;i++)
    {
        for(j=1; j<=m ;j++)
        {
            if(cost[mm[j].x] + mm[j].c < cost[mm[j].y])
            {
                cost[mm[j].y] = cost[mm[j].x] + mm[j].c;
            }
        }
    }
}


int main()
{
    read_ini();
    bellman();
    for(i=2; i<=n ;i++)
        g<<cost[i]<<" ";
    return 0;
}