#include <fstream>
#include <climits>

using namespace std;

unsigned short int N;
unsigned int M;
unsigned short int A[50001], B[50001], C[50001];

bool okay;
unsigned int i;

unsigned int sol[50001];

int main ()
{
    ifstream fin ("dijkstra.in");
    fin >> N >> M;
    for (i=1; i<=M; i++)
        fin >> A[i] >> B[i] >> C[i];
    fin.close();
    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] = UINT_MAX;
    while (okay == 0)
    {
        okay = 1;
        for (i=1; i<=M; i++)
            if (sol[B[i]] > sol[A[i]] + C[i])
            {
                sol[B[i]] = sol[A[i]] + C[i];
                okay = 0;
            }
    }
    for (i=2; i<=N; i++)
        if (sol[i] == UINT_MAX)
            sol[i] = 0;
    ofstream fout ("dijkstra.out");
    for (i=2; i<=N; i++)
        fout << sol[i] << ' ';
    fout.close();
    return 0;
}