Pasted

#include<fstream>
#include<vector>
#define inf 2000000000
using namespace std;
ifstream fin ("prog.in");
ofstream fout ("prog.out");
struct q
{
	int nod, c;
};
vector< vector<q>  > a;
vector<int> d;
vector<int> t;
vector<bool> sel;
int n;
void creare()
{
	fin>>n;
	a.resize(n+1);
	int i;
	q x;
	while(fin>>i>>x.nod>>x.c)
	{
		a[i].push_back(x);
	}
	d.resize(n+1,inf);
	t.resize(n+1);
	sel.resize(n+1);
}
void dijkstra(int sur)
{
	int i,j,k,nod;
	sel[sur]=1;
	for(i=0;i<a[sur].size();i++)
	{
		d[a[sur][i].nod]=a[sur][i].c;
		t[a[sur][i].nod]=sur;
	}
	for(i=1;i<=n;i++)
	{
		int minn;
		minn=inf;
		for(j=1;j<=n;j++)
			if(sel[j]==0&&d[j]<minn)
			{
				minn=d[j];
				nod=j;
			}
		sel[nod]=1;
		for(j=0;j<a[nod].size();j++)
			if(sel[a[nod][j].nod]==0&&d[a[nod][j].nod]>a[nod][j].c+d[nod])
			{
				d[a[nod][j].nod]=a[nod][j].c+d[nod];
				t[a[nod][j].nod]=nod;
			}
	}
}
void afisare(int nod)
{
	int no=t[nod];
	afisare(no);
	fout<<nod<<' ';
}
int main ()
{
	creare();
	dijkstra(1);
//	afisare(5);
	int nod=5;
	while(t[nod]!=1)
	{
		fout<<nod<<' ';
		nod=t[nod];
	}
	return 0;
}