#include <iostream>
#include <fstream>

using namespace std;

ifstream f ("in.txtdijkstra.in");
ofstream g("dijkstra.out");

const int inf = 1 << 30;

struct Graf {
    int nr_noduri;
    int nr_arce;
    int A[5000][5000];
};

void Citire_Graf ( Graf & X )
{
    f>>X.nr_noduri;
    f>>X.nr_arce;
    int i , x , y, z;
    for(i=1;i<=X.nr_noduri;i++)
    {
        f>>x>>y>>z;
        X.A[x][y]=z;
    }

}

void Afis ( Graf X )
{
    int i ,j;
    for(i=1;i<=X.nr_noduri;i++)
    { for(j=1;j<=X.nr_noduri;j++)
           g<<X.A[i][j]<<" ";
           g<<endl;
    }
}

void afisare (int nx ,  int x[])
{
    int i;
    for(i=3;i<=nx;i++)
        g<<x[i]<<" ";
        g<<endl;

}


void Distance_To_Vertexes ( int source , Graf X )
{
    int * visited , *costs;
    int minim;
    visited = new int[X.nr_noduri];
    costs = new int[X.nr_noduri];

    //Init

    int i;
    for (i=1;i<=X.nr_noduri;i++)
    {
        visited[i]=0;
        costs[i]=inf;
    }

    costs[source]=0;

   bool ok =true;
   while ( ok)
   {
       minim=inf;
       for(i=1;i<=X.nr_noduri;i++)
       {
           if(visited[i]==0 && costs[i]<minim)
           {
               minim=costs[i];
               source=i;
           }
       }
      if( minim<inf)
      {
       visited[source]=1;
       for(i=1;i<=X.nr_noduri;i++)
       {
           if( X.A[source][i]!=0)
           {
               if( (costs[source]+ X.A[source][i] )< costs[i] ) costs[i]=costs[source]+ X.A[source][i];
           }
       }

      } else ok=0;
   }

   afisare( X.nr_noduri , costs);

}





int main()
{
    Graf graf_a;
    Citire_Graf(graf_a );
    Distance_To_Vertexes(1 , graf_a);
    return 0;
}