#include <iostream>
#include <fstream>
using namespace std;
const int inf=100000;
int n,m,start=1,M[101][101],d[101];
bool F[101]={0};

void afisare_d()
{
    ofstream g("dijkstra.out");
    for(int i=2;i<=n;i++)
        if(d[i]==inf)
        g<<0<<" ";
    else
        g<<d[i]<<" ";

}
void citire()
{
    int x,y,l;
    ifstream f("dijkstra.in");
    f>>n>>m;
    while(!f.eof())
    {
        f>>x>>y>>l;
        M[x][y]=l;
    }
}
void init()
{
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(M[i][j]==0&&i!=j)
            M[i][j]=inf;
        }

    }
    for(int i=1;i<=n;i++)
        d[i]=M[start][i];
    d[start]=0;
    F[start]=true;
    d[0]=inf;
}
void Dijkstra()
{
    init();

    for(int i=1;i<n;i++)
    {
        int nod_minim=0;
        for(int j=1;j<=n;j++)
            if(d[nod_minim]>d[j]&&F[j]==0)
            nod_minim=j; //cel mai apropiat nod de start la un moment dat

        if(nod_minim!=0)
        {
            F[nod_minim]=1;
        for(int j=1;j<=n;j++)
        {
            if(d[nod_minim]+M[nod_minim][j]<d[j]&&F[j]==0)   //relaxarea nodului j
                {d[j]=d[nod_minim]+M[nod_minim][j];}
        }
        }
    }
}
void rezolvare()
{
    Dijkstra();
    afisare_d();
}


int main()
{

    citire();
    rezolvare();

    return 0;
}