#include<iostream>
#include<fstream>
using namespace std;
int a[100][100],n,i,infinit=1000000,s[100],x,y,m,j,cost,start,d[100],prec[100],min;


//*******************CITIREA DATELOR
//*******************GRAFUL ESTE ORIENTAT

void citire()
{ ifstream f("dijkstra.in");
f>>n>>m;// N NODURI SI M MUCHII 
           //URMEAZA M LINII CU CATE TREI VALORI PE FIECARE LINIE
           //   1 2 4       INSEAMNA ARC DE LA 1 LA 2 DE COST 4
for(i=1;i<=n;i++)
  for(j=1;j<=n;j++)  
     a[i][j]=infinit;
     
for(i=1;i<=m;i++)
{
                 f>>x>>y>>cost;
                 a[x][y]=cost;
                 }

  
 f.close();
 
 }
//*************************s
//folosim vectorii s pentru a vedea daca am selectat un nod
//s[i]=0 daca nu am selectat nodul
//s[i]=1 daca am selecta nodul

//*******************prec 
//prec[i]=j  insemna ca din nodul j vecnim in i (j precedentul lui i


//*******************d
// vectorul d imi va spune costul drumului de la nodul de start
//   d[i]=costul drumului de la nodul de start la nodul i



//*********************INITIALIZAREA VECTORILOR prec si d
void initializare()
{
     s[start]=1;
       for(i=1;i<=n;i++)
          if (a[start][i]!=infinit)   {d[i]=a[start][i];prec[i]=start;}
          else d[i]=infinit;
          
          }
          
          
 //*********************DIJKSTRA         
void dijkstra()
{int gasit,min,k;
     do{
           gasit=0;
           min=infinit;
            for(i=1;i<=n;i++)
              
                             if (s[i]==0&&d[i]<min)
                                {
                                                   min=d[i];
                                                   k=i;
                                                   gasit=1;
                                                  
                                                   }//if
                                s[k]=1;
                                
                                for(i=1;i<=n;i++)
                                  if (d[i]>d[k]+a[k][i])
                                   {
                                                        prec[i]=k;
                                                        d[i]=d[k]+a[k][i];
                                                        }//if
         
              }
                                                        while (gasit==1);
                                                        
}//sf functie dijkstra
  
  
//******************AFISAREA VECTORULUI d
   
void afisare()
{
     for(i=2;i<=n;i++)
        cout<<d[i]<<" ";
        
        }
        
        
//*************iN CAZUL IN CARE SE CERE AFISAREA DRUMULUI DE COST MINIM 
//DE LA NODUL DE START PANA LA UN ANUMIT NOD       
     void afisare_drum(int nod)
     {
        
          if (nod!=start)
            {
             afisare_drum(prec[nod]);
             cout<<" "<<nod;
             }
             }
int main()
{
    citire();//am pus in ahiva si fisierul de intrare 
             // este acelasi fisier cu cel de pe infoarena
    
    cout<<"start=";
    cin>>start;
    
    initializare();
    
    dijkstra();
    
    afisare();//afisam vectorul d
    

    cout<<endl<<"exemplu:drumul pana la nodul ...3:  "<<start;
    afisare_drum(3);
    
    
    system("pause");
    return 0;
}