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



fstream f2("dijkstra.in");
int citire()
{   int m,p,q,asdf;
    f2>>asdf; f2>>n;
    for(int i=1;i<=n;i++){
        f2>>m; f2>>p; f2>>q;
        C[m][p]=q;
        C[p][m]=q;
    } return 0;
}



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


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 0;
}

int dijkstra()
{
    int amverificattot=0,k=1;
    while(amverificattot==0)
    {
       for(int i=1;i<=n;i++)
        {  //verific 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 0;

}

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


return 0;
}