// Dijkstra's shorthest path algorithm
// Code by Cristian "Dr.Optix" Dinu <[email protected]>

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

using namespace std;

#define INF 0xFFFFFFFF

struct Edge {
	int y, cost;
};

int nodes, edges, dist[50001];
vector<Edge> graph[50001];
queue<int> q;

ifstream fin("data.in");
ofstream fout("data.out");

int main(int argc, char** argv) {
	int x, y, cost;
	Edge e;
	
	// Read data
	fin >> nodes >> edges;
	for (int i = 1; i <= edges; ++i) {
		fin >> x >> e.y >> e.cost;
		graph[x].push_back(e);
	}
	
	// Output the graph
	for (int i = 1; i <= nodes; ++i) {
		cout << i << ": ";
		for (int j=0; j < graph[i].size(); ++j) {
			cout << graph[i][j].y << ", ";
		}
		cout << endl;
	}
	
	// Dijkstra
	for (int i = 2; i <= nodes; ++i) {
		dist[i] = INF;
	}
	dist[1] = 0;
	q.push(1);
	
	while (!q.empty()) {
		int x = q.front(); 
		
		for(int i = 0; i < graph[x].size(); ++i) {
			int y = graph[x][i].y; 
			int cost = graph[x][i].cost; 
			
			if (dist[y] > dist[x] + cost) {
				dist[y] = dist[x] + cost;
				q.push(y);
			}				
		}
		
		q.pop(); 
	}
	
	// Write the output
	for (int i = 2; i <= nodes; ++i) {
		if (dist[i] != INF) {
			fout << dist[i] << ", ";
		} else {
			fout << "0 ";
		}
	}
}