#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#define inf 1e9 + 1
using namespace std;
ifstream f("dijkstra.in");
ofstream of("dijkstra.out");

vector< vector< pair<int, int> > > lista;
vector<int> d;
priority_queue< pair<int, int>, vector< pair<int, int> >, greater< pair<int, int> > > coada;

int n;
void dijkstra(int start) {
    d.assign( n + 1, inf );
    d[start] = 0;

    coada.push( make_pair( 0, start ) );
    while( !coada.empty() )  {
        pair<int, int> front = coada.top();
        coada.pop();

        int nod = front.second;
        int distanta = front.first;

        if( distanta > d[nod] )
            continue;

        for(int j = 0; j < lista[nod].size(); j++) {
            pair<int, int> vecin = lista[nod][j];

            if( d[vecin.first] > d[nod] + vecin.second ) {
                d[vecin.first] = d[nod] + vecin.second;
                coada.push( make_pair( d[vecin.first], vecin.first ) );
            }
        }
    }
    for(int j = 2; j <= n; j++)
        if( d[j] == inf ) of << 0 << " ";
    else of << d[j] << " ";
}

int main()
{
    int m, i, j, k, c;
    f >> n >> m;

    lista.assign( n + 1, vector< pair<int, int> >() );

    for(k = 0; k < m; k++) {
        f >> i >> j >> c;
        lista[i].push_back( make_pair( j, c ) );
    }

    dijkstra(1);

    return 0;
}