/*ruleaza pe mingw daca vrei pe borland c++ sterge using namespace std !!!(si pune void main in loc de int main)*/
#include<iostream.h>
#include<fstream.h>
using namespace std;
ifstream fin("date.in");
ofstream fout("date.out");
int maxint=100000, mp[100][100],i,j,nrarc,n;
int s[100], d[100],t[100];
void read_ind()
{int p,s,c;
fin>>n;
fin>>nrarc;

for(i=1;i<=nrarc;i++)
{
fin>>p;
fin>>s;
fin>>c;
mp[p][s]=c;
}
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{if(mp[i][j]==0 &&i!=j) mp[i][j]=maxint;
}
}
}
void read_dir()
{ fin>>n;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
fin>>mp[i][j];
}
void afis()
{fout<<endl;
for(i=1;i<=n;i++)
if(d[i]<maxint)fout<<d[i]<<'\t';
else fout<<"00"<<'\t';
fout<<endl;
for(i=1;i<=n;i++)
fout<<t[i]<<'\t';
fout<<endl;
for(i=1;i<=n;i++)
	fout<<s[i]<<'\t';
}
void write(int mp[100][100])
{
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++) 
if(mp[i][j]<maxint)fout<<mp[i][j]<<'\t';
else fout<<"00"<<'\t';
fout<<endl;
}
}
void dij_init(int r)
{   for(i=1;i<=n;i++)
{
s[i]=0;
d[i]=0;
t[i]=0;
}
for(i=1;i<=n;i++)
  d[i]=mp[r][i];
d[0]=maxint;//initializeaza d[0] cu 00 pentru aflarea pozitiei minimului
s[r]=1;

for(i=1;i<=n;i++)
if(mp[r][i]>0 && mp[r][i]<maxint) t[i]=r;
}
int dij_min()
{   d[0]=maxint;
	int poz=0;
for(i=1;i<=n;i++)
if(s[i]==0 && d[i]>d[poz]) poz=i;
if(d[poz]>=maxint) for(i=1;i<=n;i++) if(s[i]==0) {poz=i;return poz;}
return poz;
}
int min(int a,int b)
{
if(a<b) return a;
return b;
}
void dijkastra(int r)
{ fout<<endl; 
	int nrsel=1,poz=0;
dij_init(r);
//afis();
while(nrsel<n)
{s[poz]=1;
poz=dij_min();

nrsel++;

for(i=1;i<=n;i++)
{
if(d[i]>d[poz]+mp[poz][i])
{d[i]=d[poz]+mp[poz][i];
t[i]=poz;
}//if

}//for
//fout<<endl;
//fout<<poz<<endl;
//afis();
}//while

}
void read()
{
int nr;
cout<<"Moduri de citire:"<<endl;
cout<<"1.citire indirecta(citirea arcelor)"<<endl;
cout<<"2.citire directa(citirea matricii ponderilor)"<<endl ;
cout<<"alege numarul:";
cin>>nr;
if (nr==1) read_ind();
else read_dir();
}


int main()
{int r;   
read();
write(mp);
cout<<"nodul din care vrei sa pornesti:";
cin>>r;
dijkastra(r);
afis();
int m=2;
for(i=1;i<=n;i++)
{m=i;	
while(m!=0)
{fout<<m<<'\t';
m=t[m];
}
fout<<endl;
}

}

/*algoritmul lui dijkastra pentru alflarea drumului minim*/