#include<iostream>
#include<fstream>
using namespace std;
int n,m;
int P[100],D[100],C[100][100];
fstream f("dijkstra.in");
ofstream g("dijkstra.out");
int i,j,k;

int citirecosturi()
{
    f>>n; f>>m;
    for(int i=0;i<=m;i++)
    { int a,b,c;
        f>>a>>b>>c;
        C[a][b]=c;
    }


    /*f>>n;
    for(k=1;k<=n;k++)
    {
        for(i=1;i<=n;i++)
        f>>C[k][i];
    }*/
    return true;
}


int showme()
{
   // cout<<endl<<"Distanta este:"<<endl;
        for(int i=2; i<=n; i++)
        {  g<<P[i]<<" ";   }
        return true;
}


int init()
{
    for (int i=2;i<=n;i++)
    {   P[i]=2000000; // verific daca am initializat corect
        //nodul de start are costul 0 iar celelalte infinit
        if(C[1][i]==0) {D[i]= 2000000;}
        else           {D[i]=C[1][i];}
    }
    return true;
}

int dijkstra()
{
    int amverificattot=0,k=1;
    while(amverificattot==0)
    {
       for(int i=1;i<=n;i++)
        { //verifica daca exista cost spre alte noduri,adica ce muchii pornesc din acel nod
         //pentru acele noduri daca costul gasit(pe care l-am adunat cand am parcurs) este mai mic decat cel existent
        //.. daca da,depune noul cost in pozitia caracteristica nodului curent in vectorul D
            if(C[k][i]!=2000000 && C[k][i]!=0)
            {
                if(C[k][i]<P[i] && k==1) {P[i]=C[k][i];}
                if(C[k][i]+P[k]<P[i] && P[i]!=0) {P[i]=P[k]+C[k][i];}
            }
        }
    k++;
    if(k==n)
        amverificattot=1;
    }
    return true;

}

int main()
{
    citirecosturi();
    init();
    dijkstra();
    showme();


}