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

#define NMAX 50005
#define INF (1 << 29)

using namespace std;

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

int d[NMAX];
vector<pair<int,int>> graf[NMAX]; // node + cost
priority_queue<pair<int,int>, vector<pair<int,int>>, comparator> q; // cost + node
 
int main() {
    int N, M, A, B, C;

    ifstream in("dijkstra.in");
    in >> N >> M;
 
    for (int i = 0 ; i < M ; i++) {
        in >> A >> B >> C;
        graf[A].push_back(make_pair(B, C));
    }

    for (int i = 2; i <= N; i++) {
    	d[i] = INF;
    }
 
    d[1] = 0;
     
    q.push(make_pair(0,1));
 
    while(!q.empty()) {
        int node = q.top().second;
        int dist = q.top().first;

	q.pop();

	if (dist > d[node]) {
		continue;
	}

        for (pair<int,int> n : graf[node]) {
            if (d[n.first] > d[node] + n.second) {
                
		d[n.first] = d[node] + n.second;
                q.push(make_pair(d[n.first], n.first));
            }
        }
    }

    ofstream out("dijkstra.out");

    for (int i = 2 ; i <= N ; i++) {
        if (d[i] == INF) {   
            out << 0 << " ";
	
	} else {
	    out << d[i] << " ";
	}
    }
 
    in.close();
    out.close();
 
    return 0;
}