#include <stdio.h>
#include <vector>
#include <queue>
using namespace std;

int n,m;
vector<pair<int,int> > adj[10000];
int d[10000];

int main() {
	freopen("test.in","r",stdin);
	scanf("%d %d",&n,&m);
	for (int i=0;i<m;i++) {
		int a,b,c;
		scanf("%d %d %d",&a,&b,&c);
		adj[a].push_back({b,c});
		adj[b].push_back({a,c});
	}
	for (int i=1;i<=n;i++) d[i]=1e9;
	d[1]=0;
	priority_queue<pair<int,int> > pq;
	pq.push({0,1});
	while (!pq.empty()) {
		pair<int,int> p=pq.top();
		pq.pop();
		int x=p.second, dx=-p.first;
		if (dx!=d[x]) continue;
		for (pair<int,int> yc : adj[x]) {
			int y=yc.first, c=yc.second;
			if (d[x]+c<d[y]) {
				d[y]=d[x]+c;
				pq.push({-d[y],y});
			}
		}
	}
	for (int i=1;i<=n;i++) {
		printf("%d: %d\n",i,d[i]);
	}
	return 0;
}