#include <bits/stdc++.h>

using namespace std;

#define pp pair<int, int>
#define pb push_back
#define x first
#define y second

const int NMAX = 50009;
const int INF = 0x3f3f3f3f;

int n, m;

vector< pp > g[NMAX];
int dist[NMAX];


void read() {

    cin >> n >> m;

    for(int i = 1; i <= m ; ++i) {
        int x, y, c;
        cin >> x >> y >> c;
        g[x].pb({y, c});
    }
}

void dijsktra(vector<pp>* g, int start, int* dist) {

    priority_queue< pp , vector< pp >, greater< pp > > pq;

    for(int i = 0 ; i <= n ; ++i)
        dist[i] = INF;

    dist[start] = 0;
    pq.push({dist[start], start});

    while(!pq.empty()) {

        int node = pq.top().y;
        int d = pq.top().x;
        pq.pop();

        if(dist[node] < d) continue;

        for(pp p : g[node])
            if(dist[p.x] > dist[node] + p.y) {

                dist[p.x] = p.y  + dist[node];
                pq.push({dist[p.x], p.x});
            }
    }
}

int main() {

    freopen("dijkstra.in", "r", stdin);
    freopen("dijkstra.out", "w", stdout);

    read();

    dijsktra(g, 1, dist);

    for(int i = 2; i <= n; ++i)
        if(dist[i] == INF)
            cout << -1 << ' ';
        else
            cout << dist[i] << ' ';
    cout << '\n';

}