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