#include <fstream>
#include <climits>

using namespace std;

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

unsigned int N, M;
unsigned int A[250001], B[250001], C[250001];

bool ok;
unsigned int i;

unsigned int sol[50001];

int main ()
{
    fin >> N >> M;
    for (i=1; i<=M; i++)
        fin >> A[i] >> B[i] >> C[i];
    for (i=1; i<=M; i++)
        if (A[i] == 1)
            sol[B[i]] = C[i];
    for (i=2; i<=N; i++)
        if (sol[i] == 0)
            sol[i] = INT_MAX;
    while (ok == 0)
    {
        ok = 1;
        for (i=1; i<=M; i++)
            if (sol[B[i]] > sol[A[i]] + C[i])
            {
                sol[B[i]] = sol[A[i]] + C[i];
                ok = 0;
            }
    }
    for (i=2; i<=N; i++)
        if (sol[i] == INT_MAX)
            sol[i] = 0;
    for (i=2; i<=N; i++)
        fout << sol[i] << ' ';
    return 0;
}