/*
Algoritmul lui Dijkstra
Se da un graf orientat cu N noduri si M arce.

Cerinta
Sa se determine lungimea minima a drumului de la nodul 1 la fiecare din nodurile 2, 3, ..., N-1, N si sa se afiseze aceste lungimi. Lungimea unui drum este data de suma lungimilor arcelor care constituie drumul.

Date de intrare
Fisierul de intrare dijkstra.in contine pe prima linie numerele N si M, separate printr-un spatiu, cu semnificatia din enunt. Urmatoarele M linii contin, fiecare, cate 3 numere naturale separate printr-un spatiu A B C semnificand existenta unui arc de lungime C de la nodul A la nodul B.

Date de iesire
In fisierul de iesire dijkstra.out veti afisa pe prima linie N-1 numere naturale separate printr-un spatiu. Al i-lea numar va reprezenta lungimea unui drum minim de la nodul 1 la nodul i+1.

Restrictii
1 ≤ N ≤ 50 000
1 ≤ M ≤ 250 000
Lungimile arcelor sunt numere naturale cel mult egale cu 20 000.
Pot exista arce de lungime 0
Nu exista un arc de la un nod la acelasi nod.
Daca nu exista drum de la nodul 1 la un nod i, se considera ca lungimea minima este 0.
Arcele date in fisierul de intrare nu se repeta.
*/
#include <bits/stdc++.h>
#define NMAX 50005
#define pb push_back

using namespace std;

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

struct A
{
    int cost, dest;
};

vector < A > v[NMAX];
multimap < int, int > b;

int main()
{
    vector < A > :: iterator it;
    int n, m, x, y, z, i, r[NMAX];

    fin >> n >> m;
    while ( m-- )
    {
        fin >> x >> y >> z;
        v[x].pb ( { z, y } );
    }

    r[1] = 0;
    for ( i = 2; i <= n; i++ ) r[i] = INT_MAX;

    b.insert ( { 0, 1 } );
    while ( b.empty() == 0 )
    {
        x = b.begin() -> second;
        b.erase ( b.begin() );

        for ( it = v[x].begin(); it != v[x].end(); it++ )
            if ( r[x] + (*it).cost < r[(*it).dest] )
            {
                r[(*it).dest] = r[x] + (*it).cost;
                b.insert ( { r[(*it).dest], (*it).dest } );
            }
    }

    for ( i = 2; i <= n; i++ )
    {
        if ( r[i] != INT_MAX ) fout << r[i] << ' ';
        else fout << 0 << ' ';
    }

    return 0;
}

/*
IN:
5 6
1 2 1
1 4 2
4 3 4
2 3 2
4 5 3
3 5 6

OUT:
1 3 2 5
*/