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

using namespace std;

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

int main(){
	int n, m;
	f >> n >> m;
	cout << n << ' ' << m;

	vector < vector < pair < int, int > > > graf(n+1);
	vector < int > dist(n+1, 1<<20);
	vector < int > viz(n+1, 0);
	for(int i = 0; i < m; i++){
		int x, y, cost;
		f >> x >> y >> cost;
		graf[x].push_back(make_pair(y, cost));
	}
    dist[1] = 0;
	for(int i = 1; i <= n; i++){

		int min = 1<<20, poz = 1;
		for(int j = 1; j <= n; j++)
			if(dist[j] < min and viz[j] == 0)
			{
				min = dist[j];
				poz = j;
			}
		viz[poz] = 1;
		for(auto muchie: graf[poz]){
			if(muchie.second + dist[poz] < dist[muchie.first]) dist[muchie.first] = muchie.second + dist[poz];
		}
	}

	for(int i = 2; i <= n; i++)
        if(dist[i]!=1<<20) g << dist[i] << ' ';
            else g << "0 ";

	return 0;
}