#include <iostream>
#include <fstream>
using namespace std;

//ifstream fin("dijkstra.in");
//ofstream fout("dijkstra.out");

ifstream fin("date.in");

struct nod
{
	int cost, index;
	nod *urm, *ultim;
};
nod *prim[50000];// = new nod();

int c[50000], n, m;
int Pinfinit = 1.e20;

void dij(int nodDat, int val)
{
	int next[50000];
	int nr = 0;
	nod *p = prim[nodDat];
	while(p)
	{
		if(p->cost + val < c[p->index])// && viz[i] == 0)
		{
			c[p->index] = p->cost + val;
			//viz[i] = 1;
			//t[i] = nod;
			next[nr] = p->index;
			nr++;
			///dij(p->index, c[p->index]);
		}

		p = p->urm;
	}

	for(int i = 0; i < nr; i++)
	{
		dij(next[i], c[next[i]]);
	}
//	for(int i = 1; i <= n; i++)
//	{
//		if(nod != i && a[nod][i] != Pinfinit && a[nod][i] + val < c[i])// && viz[i] == 0)
//		{
//			c[i] = a[nod][i] + val;
//			//viz[i] = 1;
//			//t[i] = nod;
//
//			dij(i, c[i]);
//		}
//	}
}

int main()
{
	fin>>n>>m;
	int x, y, cost, nodPlecare = 1;

//	for(int i = 1; i <= n; i++)
//	{
//		for(int j = 1; j <= n; j++)
//		{
//			if(i != j)
//			{
//				//a[i][j] = Pinfinit;
//			}
//		}
//		c[i] = Pinfinit;
//	}
	while(fin>>x>>y>>cost)
	{
		nod *p = new nod();
		p->cost = cost;
		p->index = y;
		p->urm = NULL;

		if(!prim[x])
		{
			prim[x] = new nod();

			prim[x]->urm = p;
		}
		else
		{
			prim[x]->ultim->urm = p;
		}
		c[y] = Pinfinit;

		prim[x]->ultim = p;


		///a[x][y] = cost;
	}
	c[nodPlecare] = 0;



	dij(nodPlecare, 0);

	for(int i = 2; i <= n; i++)
	{
		if(c[i] != Pinfinit)
		{
			cout<<i<<": "<<c[i]<<'\n';
//			fout<<c[i]<<' ';
		}
		else
		{
			cout<<i<<": "<<0<<'\n';
//			fout<<"0 ";
		}
	}

    return 0;
}





//#include <iostream>
//#include <fstream>
//using namespace std;
//
//ifstream fin("date.in");
//
//int c[100], t[100], a[100][100], n, m;
//int Pinfinit = 1.e20;
//
//void dij(int nod, int val)
//{
//	for(int i = 1; i <= n; i++)
//	{
//		if(nod != i && a[nod][i] != Pinfinit && a[nod][i] + val < c[i])// && viz[i] == 0)
//		{
//			c[i] = a[nod][i] + val;
//			//viz[i] = 1;
//			//t[i] = nod;
//
//			dij(i, c[i]);
//		}
//	}
//}
//
//int main()
//{
//	fin>>n>>m;
//	int x, y, cost, nodPlecare = 1;
//
//	for(int i = 1; i <= n; i++)
//	{
//		for(int j = 1; j <= n; j++)
//		{
//			if(i != j)
//			{
//				a[i][j] = Pinfinit;
//			}
//		}
//		c[i] = Pinfinit;
//	}
//	c[nodPlecare] = 0;
//
//	while(fin>>x>>y>>cost)
//	{
//		a[x][y] = cost;
//	}
//
//
//	//viz[nodPlecare] = 1;
//	dij(nodPlecare, 0);
//
//	for(int i = 2; i <= n; i++)
//	{
//		cout<<i<<": "<<c[i]<<'\n';
//	}
//
//    return 0;
//}