#include <iostream>
#include <fstream>
#include <vector>
#include <queue>


using namespace std;
#define nmax 500005

vector <int> edges[nmax], price[nmax];

int viz[nmax];

struct info{
    int cost, v;
    bool operator < ( const info& x) const {
        return cost > x.cost;
    }
};

priority_queue <info> pq;

int main()
{
    ifstream cin("dijkstra.in");
    ofstream cout("dijkstra.out");
    int n, m, a, b, c, i;
    info x, y;
    cin >> n >> m;

    for( i = 0; i < m; i++ ) {
        cin >> a >> b >> c;
        edges[a].push_back(b);
        price[a].push_back(c);
    }

    for( i = 1; i <= n; i++ )
        viz[i] = -1;

    x.v = 1;
    x.cost = 0;
    viz[x.v] = x.cost;
    pq.push(x);

    while( pq.size() > 0 ) {
        x = pq.top();
        //cout << x.v << " " << x.cost;
        for( i = 0; i < edges[x.v].size(); i++ ) {
            if( viz[edges[x.v][i]] == -1 || viz[edges[x.v][i]] > x.cost + price[x.v][i] ) {
                viz[edges[x.v][i]] = x.cost + price[x.v][i];
                y.cost = viz[edges[x.v][i]];
                y.v = edges[x.v][i];
                //cout << "... " << y.v << " " << y.cost << " ...";
                pq.push(y);
            }
        }
        //cout << "\n";
        pq.pop();
    }

    for( i = 2; i <= n; i++ )
        cout << max(0, viz[i]) << " ";
    return 0;
}