#include <fstream>

using namespace std;

ifstream fin ("dijkstra.in");
ofstream fout ("dijkstra.out");

#define NMAX 5001
#define INF 0x3f3f3f3f

int n, m, c[NMAX][NMAX], x, y, cst;
int viz[NMAX], d[NMAX];
//int tata[NMAX];

void dijkstra(int x0)
{
    int mn, k, ok;

    for (int i = 1; i<=n; i++)
    {
        d[i] = c[x0][i];
       // tata[i] = x0;
        viz[i] = 0;
    }
    //tata[x0] = 0;
    viz[x0] = 1;
    ok = 1;
    while (ok)
    {
        mn = INF;
        for (int i = 1; i <= n; i++)
            if (!viz[i] && mn > d[i])
            {
                mn = d[i];
                k = i;
            }
        if (mn != INF)
        {
            viz[k] = 1;
            for (int i = 1; i <= n; i++)
               if (!viz[i] && d[i] > d[k] + c[k][i]) d[i] = d[k] + c[k][i];

        }
        else ok = 0;
    }
}
int main()
{
    fin >> n >> m;

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            if (i!=j)c[i][j]=INF;

    for (int i = 1; i <= m; i++)
    {
        fin >> x >> y >> cst;
        c[x][y] = cst;
    }
    dijkstra(1);

    for (int i = 2; i <= n; i++)fout << d[i] << ' ';
    return 0;
}