#include<fstream>
#include<iostream>
#define inf "dijkstra.in"
#define outf "dijkstra.out"
#define MaxN 20001
#define PINF 0x3f3f3f3f
using namespace std;

fstream f(inf,ios::in),g(outf,ios::out);

int MP[MaxN][MaxN];
int D[MaxN];
int S[MaxN];
int T[MaxN];
int r=1; // Sursa de la care calculez drumurile
int N,M;

void Citire()
{
int c;
//f>>N>>M>>r;
f>>N>>M;
for(int i=1;i<=N;i++)
    for(int j=1;j<=N;j++){MP[i][j]=PINF;if(i==j)MP[i][j]=0;}
int i,j;
while(f>>i>>j>>c)
    {
    MP[i][j]=c;
    }
}

void Drum(int i)
{
if(T[i])Drum(T[i]);
g<<i<<" ";
}

void Dijkstra()
{
int poz,min;
S[r]=1;
for(int i=1;i<=N;i++)
    {
    D[i]=MP[r][i];
    if(r!=i)
        if(MP[r][i]<PINF)T[i]=r;
    }
for(int i=1;i<=N-1;i++)
    {
    min=PINF;
    for(int j=1;j<=N;j++)
        if(S[j]==0)
            if(D[j]<min)
                {
                min=D[j];
                poz=j;
                }
    S[poz]=1;
    for(int j=1;j<=N;j++)
        if(S[j]==0)
            if(D[j]>D[poz]+MP[poz][j])
                {
                D[j]=D[poz]+MP[poz][j];
                T[j]=poz;
                }
    }
for(int i=2;i<=N;i++)g<<D[i]<<" ";
g<<endl;
//Drum(4);
}

int main()
{
Citire();
Dijkstra();
f.close();
g.close();
return 0;
}