/**
Varianta Dijksta infoarena

*/

///Presupuneri despre graf(faza cu n-1 ori la for)???
#include <iostream>
#include <fstream>
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

#define pinf 1e+38
float minn;
int viz[51];
int n,m,k=1,i,j,a[51][51],d[51],t[51];
/**
void drum(int i)
{
    if(t[i]) drum(t[i]);
    g<<i<<" ";
}
*/
int main()
{
f>>n>>m;
///Trecem toata matricea pe -1

for(int i=1;i<=n;i++)
    for(j=1;j<=n;j++)
        a[i][j]=-1;

///Citim cele m muchii
int A,B,LUNG;
    for(j=1;j<=m;j++)
{       f>>A>>B>>LUNG;
        a[A][B]=LUNG;

}

viz[k]=1;
///Initializare punct de pornire

for(i=1;i<=n;i++)
    d[i]=pinf;

for(i=1;i<=n;i++)
{
    if(a[k][i]!=-1) {
        d[i]=a[k][i];
        t[i]=k;
    }
}


int poz;
///Cautam cel mai apropiat nod(nevizitat) la care putem ajunge si calculam distantele prin el
for(i=1;i<=n-1;i++)
{
///CALCULAM  NODUL CEL MAI APROPIAT
minn=pinf;
for(j=1;j<=n;j++)
    if(viz[j]==0&&minn>d[j]) {   minn=d[j];
                                poz=j;
                            }


viz[poz]=1;
///ACTUALIZAM DISTANTELE PRIN CEL MAI APROPIAT NOD NEVIZITAT Atat timp cat avem drum
for(j=1;j<=n;j++)
if(viz[j]==0) if(d[j]>d[poz]+a[poz][j]&&a[poz][j]!=-1) {
                                            d[j]=d[poz]+a[poz][j];
                                            t[j]=poz;
                                            }

}

int aux=pinf;///d[i] este int si nu ia valoarea pinf
///ia val max a int asa ca aux o sa fie val max
for(i=1;i<=n;i++)
   if(d[i]<aux)  g<<d[i]<<" ";

f.close();
g.close();
    return 0;
}