#include <fstream>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
typedef pair<int,int> ii;
const int inf=1<<30;
vector<int> dist, heap, pos;
template <class T> void pvec(vector<T> &vec) {
	for (size_t i=0; i<vec.size(); ++i)
		cout << vec[i] << ' '; cout << '\n';
}

inline bool cmp(int a, int b) {
	return dist[a]>=dist[b];
}

void heap_swap(int node1, int node2) {
	swap(pos[heap[node1]],pos[heap[node2]]);
	swap(heap[node1],heap[node2]);
}

int main() {
	ifstream fin("dijkstra.in");
	ofstream fout("dijkstra.out");
	int n, nedge;
	fin >> n >> nedge;
	vector<vector<ii> > adjlist(n+1);
	for (int i=0,v1,v2,weight; i<nedge; ++i) {
		fin >> v1 >> v2 >> weight;
		adjlist[v1-1].push_back(ii(v2-1,weight));
	}
	heap.resize(2*n+1), pos.resize(n+1);
	for (int i=0; i<n; ++i) {
		heap[i]=i;
		pos[i]=i;
	}
	for (int i=n; i<=2*n; ++i) heap[i]=n;
	dist.assign(n+1,inf);
	dist[0]=0;
	dist[n]=inf+1;
	vector<ii>::iterator it;
	while (dist[heap[0]]<inf) {
		//cout << heap[0] << '\n';
		for (it=adjlist[heap[0]].begin(); it!=adjlist[heap[0]].end(); ++it) {
			int v=it->first;
			if (pos[v]==0) continue;
			dist[v]=min(dist[v], dist[heap[0]]+it->second);
			while (!cmp( v, heap[ (pos[v]-1)>>1 ] )) {
				heap_swap( pos[v], (pos[v]-1)>>1 );
			}
		}
		//pvec(heap);
		//cin.get();
		heap[0]=n;
		pos[n]=0;
		int temp;
		while (min(dist[heap[2*pos[n]+1]], dist[heap[2*pos[n]+2]])<=inf) {
			if (cmp(heap[2*pos[n]+1], heap[2*pos[n]+2])) temp=2*pos[n]+2;
			else temp=2*pos[n]+1;
			//cout << del << ' ' << heap[del] << '\n';
			//cout << temp << ' ' << heap[temp] << '\n';
			//cin.get();
			heap_swap(pos[n],temp);
		}
	}
	pvec(heap);
	//for (int i=0; i<n; i++) {
		//cout << dist[heap[i]] << ' ';
	//}
	//cout << '\n';
	for (int i=1; i<n; ++i) if (dist[i]!=inf && pos[i]!=0) cout << i << ' ' << pos[i] << '\n';
	for (int i=1; i<n; ++i) fout << (dist[i]==inf ?0 :dist[i]) << ' ';
	return 0;
}