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

using namespace std;

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

const int NMAX = 50001;
const int INF = (1 << 24);

int n, m, d[NMAX];
vector < pair<int, int> > G[NMAX];

void read() {

    f >> n >> m;

    while(m--) {
        int x, y, cost;
        f >> x >> y >> cost;
        G[x].push_back({y, cost});
    }
}

struct Pq_Comparator {
    bool operator()(const pair<int,int>& a,const pair<int,int>& b) {
        return a.first > b.first;
    }
};

void dijkstra(const int& sourceVertex) {

    priority_queue < pair<int,int>, vector<pair<int,int>>, Pq_Comparator > pq;
    pq.push( { 0, sourceVertex } );

    for(int i = 1;i <= n;++i)
        d[i] = INF;

    d[sourceVertex] = 0;

    while(!pq.empty()) {

        const int node = pq.top().second;
        pq.pop();

        for(pair<int,int> neighbour : G[node]) {
            // neighbour.first = the actual neighbour of the vertex 'node'
            // neighbour.second = the cost to get from 'node' to its current neighbour
            if(d[node] + neighbour.second < d[neighbour.first]) {
                d[neighbour.first] = d[node] + neighbour.second;
                pq.push( { d[neighbour.first], neighbour.first } );
            }
        }
    }
}

void print() {

    for(int i = 2;i <= n;++i)
        g <<  (d[i] == INF ? -1 : d[i]) << " ";
}

int main() {

    read();
    dijkstra(1);
    print();

    return 0;
}