#include <fstream>
#include <climits>

using namespace std;

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

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

bool okay;
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 (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++)
        fout << sol[i] << ' ';
    return 0;
}