#include<fstream>
#include<vector>
#include<iostream>
using namespace std;
int n,n1,m,d[50010],H[50010],poz[50010];
struct Muchie{int nod,cost;};
vector <Muchie> G[50010];

void Citire()
{
	int i,x,y,c;
	Muchie aux;
	ifstream fin("dijkstra.in");
	fin>>n>>m;
	n1=n;
	for(i=1;i<=m;i++)
	{
		fin>>x>>y>>c;
		aux.nod=y; aux.cost=c;
		G[x].push_back(aux);
	}
	fin.close();
}

void CombHeap(int i,int n)
{
	int x,tata,fiu;
	tata=i;
	fiu=2*i;
	x=H[tata];
	while(fiu<=n)
	{
		if(fiu<n)
			if(d[H[fiu]]>d[H[fiu+1]])
				fiu++;
		if(d[x]>d[H[fiu]])
		{
			H[tata]=H[fiu];
			poz[H[fiu]]=tata;
			tata=fiu;
			fiu=fiu*2;
		}
		else
			fiu=n+1;
	}
	H[tata]=x;
	poz[x]=tata;
}

int ExtractMin()
{
	int sol=H[1];
	H[1]=H[n--];
	CombHeap(1,n);
	return sol;
}

void Urca(int fiu,int x)
{
	int tata=fiu/2;
	while(tata && d[H[tata]]>d[fiu])
	{
		H[fiu]=H[tata];
		poz[H[tata]]=fiu;
		fiu=tata;
		tata=fiu/2;
	}
	H[fiu]=x;
	poz[x]=fiu;
}

void Creare_Heap()
{
	int i;
	for(i=1;i<=n;i++)
	{
		H[i]=i;
		poz[i]=i;
	}
	for(i=n/2;i>0;i--)
		CombHeap(i,n);
}

void Dijkstra()
{
	int i,j,vfmin,dmin;
	Muchie aux;
	for(i=2;i<=n;i++)
		d[i]=2000000000;
	d[1]=0;
	Creare_Heap();
	for(i=1;i<=n;i++)
		cout<<H[i]<<' '<<d[H[i]]<<"\n";
	for(i=1;i<=n;i++)
		cout<<poz[i]<<' ';
	for(i=1;i<=n;i++)
	{
		vfmin=ExtractMin();
		dmin=d[vfmin];
		for(j=0;j<G[vfmin].size();j++)
		{
			aux=G[vfmin][j];
			if(d[aux.nod]>dmin+aux.cost)
			{
				d[aux.nod]=dmin+aux.cost;
				Urca(poz[aux.nod],aux.nod);
			}				
		}
	}
}

void Afisare()
{
	int i;
	ofstream fout("dijkstra.out");
	for(i=2;i<=n1;i++)
		fout<<d[i]<<' ';
	fout<<"\n";
	fout.close();
}

int main()
{
	Citire();
	Dijkstra();
	Afisare();
	return 0;
}