#include<iostream>
#include<fstream>

using namespace std;
int n,m;
int P[100],D[100],C[100][100];
int i,j,k;

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");


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;
    }
    return true;
}

int showme()
{
        for(int i=2; i<=n; i++)
          g<<P[i]<<" ";

        return true;
}


int init()
{
    for (int i=2;i<=n;i++)
    {   P[i]=2000000;

        if(C[1][i]==0) {D[i]= 999;}
        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++)
        {
            if(C[k][i]!=999 && 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();

}