#include<fstream>
#include<iostream>
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
long int n,c[10000][10000],s[10000],t[10000],r,cmin,poz,m;
const int inf=30000;
void citire()
{
    int i,j,k,cost;
    f>>n>>m;
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
        c[i][j]=inf;
    for(i=1;i<=m;i++)
    {
        f>>j>>k>>cost;
        c[j][k]=cost;
    }
}
void dijkstra(int r)
{
    int i,j,d[100];
     citire();
    //r=1;
    for(i=1;i<=n;i++)
        d[i]=0;
    for(i=1;i<=n;i++)
    {
        d[i]=c[r][i];
        if(i!=r)
        if(d[i]<inf)
        t[i]=r;
    }
s[r]=1;
for(i=1;i<n;i++)
{
    cmin=inf;
    for(j=1;j<=n;j++)
    if(d[j]<cmin && s[j]==0)
    {
        cmin=d[j];
        poz=j;
    }
    s[poz]=1;
    for(j=1;j<=n;j++)
    if(s[j]==0 && d[j]>d[poz]+c[poz][j])
    {
        d[j]=d[poz]+c[poz][j];
        t[j]=poz;
    }
}
for(i=2;i<=n;i++)
        g<<d[i]<<" ";
}
void drum(int i)
{
    if(t[i])
    drum(t[i]);
    g<<i<<" ";
}
int main()
{
    int i;
    //      citire();
    dijkstra(1);
    /*for(i=1;i<=n;i++)
    if(d[i]<inf && i!=r)
    {
        g<<"Drumul de la nodul "<<r<<" la nodul "<<i<<" este: ";
        drum(i);
        g<<endl;
    }
    else
    g<<"Nu exista drum de la nodul "<<i<<" la nodul "<<r;*/
    //for(i=2;i<=n;i++)
        //g<<d[i]<<" ";
return 0;
}