#include<bits/stdc++.h>
using namespace std;
int n,m,far[1001];
bool ji[1001];//是否进入集合
int ma[1001][1001];//邻阶表
int main() 
{
	memset(ma,0x3f,sizeof(ma));
	memset(far,0x3f,sizeof(far));
	cin>>n>>m;
	int a,b,c;
	for(int i=1;i<=m;i++)
	{
		cin>>a>>b>>c;
		ma[a][b]=c;
	}
	//输入
	far[1]=0;
	for(int i=1;i<=n;i++)
	{
		int t=-1;
		for(int j=1;j<=n;j++)
			if(ji[i]==0 && (t==-1 || far[j]<far[t]))
				t=j;
		ji[t]=1;
		for(int j=1;j<=n;j++)
			far[j]=min(far[j],far[t]+ma[t][j]);
	}
	//算法
	for(int i=1;i<=n;i++)
		cout<<i<<" "<<far[i]<<'\n';
	return 0;
}