#include <fstream>
#define INF 0x7fffffff

using namespace std;

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

int n, m, i, j;
struct muchie{
    int x, y, c;
}G[250002];
int d[50002];
bool ok;

int main()
{
    f >> n >> m;
    for (i = 1; i <= m; i++)
    {
        f >> G[i].x >> G[i].y >> G[i].c;
        if (G[i].x == 1)
            d[G[i].y] = G[i].c;
    }

    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].x] + G[i].c < d[G[i].y])
                d[G[i].y] = d[G[i].x] + G[i].c, ok = 0;
    }
    for (i = 2; i <= n; i++)
        g << d[i] << " ";
    return 0;
}