#include <fstream>
#include <climits>
#define InFile  "dijkstra.in"
#define OutFile "dijkstra.out"
#define MAX 250001

using namespace std;

void read ();
void solve ();
void print ();

int N;
int M;
int A[MAX], B[MAX], C[MAX];

bool okay;
int i, j;

int path[MAX];

int main ()
{
    read();
    solve();
    print();
    return 0;
}

void read ()
{
    ifstream fin (InFile);
    fin >> N >> M;
    for (i=1; i<=M; i++)
        fin >> A[i] >> B[i] >> C[i];
    fin.close();
}

void solve ()
{
    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;
            }
    }
}

void print ()
{
    ofstream fout (OutFile);
    for (i=2; i<=N; i++)
        if (path[i] != INT_MAX)
            fout << path[i] << ' ';
        else
            fout << 0 << ' ';
    fout.close();
}