/**
 * Author: Andu Scheusan (not_andu)
 * Created: 18.09.2023 20:51:24
*/

#include <bits/stdc++.h>
#pragma GCC optimize("O3")

using namespace std;

#define INFILE "dijkstra.in"
#define OUTFILE "dijkstra.out"

typedef long long ll;

const int VMAX = 50002;
const ll INF = 1000000001;

struct HeapNode {

	int node;
    int cost;

	HeapNode(int n, int c) : node(n), cost(c) {}

	bool operator<(const HeapNode &to) const {
		return cost > to.cost;
	}

};

int n, m;
ll dist[VMAX];
vector<HeapNode> adj[VMAX];

void djikstra(int source){

    for(int i = 1; i <= n; ++i){

        dist[i] = INF;

    }

    dist[source] = 0;

    priority_queue<HeapNode> q;

    q.push(HeapNode(1, 0));

    while(!q.empty()){

        int node = q.top().node;
        int cost = q.top().cost;

        // cout << "node: " << node << '\n';

        q.pop();

        if(cost != dist[node]){
            continue;
        }

        for(int i = 0; i < adj[node].size(); ++i){

            HeapNode to = adj[node][i];

            // cout << '\t' << "node: " << to.node << '\n';

            if(cost + to.cost < dist[to.node]){

                dist[to.node] = cost + to.cost;

                q.push(HeapNode(to.node, dist[to.node]));

            }

        }

    }

}

void solve(){

    cin >> n >> m;

    for(int i = 0; i < m; ++i){

        int node1, node2, price;

        cin >> node1 >> node2 >> price;

        HeapNode h(node2, price);

        adj[node1].push_back(h);

    }

    djikstra(1);

    for(int i = 2; i <= n; ++i){

        if(dist[i] != INF){

            cout << dist[i] << " ";

        }
        else{

            cout << 0 << " ";

        }

    }

}

int main(){
    
    ios_base::sync_with_stdio(false);

    freopen(INFILE, "r", stdin);
    freopen(OUTFILE, "w", stdout);

    cin.tie(nullptr);
    cout.tie(nullptr);

    solve();

    return 0;
}