#include <iostream>
#include <fstream>
#include <queue>
#define inf 0x7FFF
#define nmax 9999
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

int a[nmax][nmax],d[nmax],m[nmax],h[nmax],nr=0;

void push(int x)
{int tata,fiu;
    h[++nr]=x;
    fiu=nr;tata=nr/2;
    while(tata>0)
     if(d[h[tata]]>d[x])
       {h[fiu]=h[tata];
       fiu=tata;
       tata/=2;
       }else break;
 h[fiu]=x;
 }

int top()
{int x,tata,fiu,v=h[1];
h[1]=h[nr];nr--;
x=h[1];
tata=1;fiu=2*tata;

while(fiu<=nr)
{if(fiu<nr && d[h[fiu+1]]<d[h[fiu]])fiu++;
 if(d[x]>d[h[fiu]])
 {h[tata]=h[fiu];
  tata=fiu;
  fiu*=2;
  }
 else break;
}
h[tata]=x;
return v;}

int hempty()
{
    return nr==0;
}


int main()
{int x,y,c,n,nri,i,j,vf,dmin;
    fin>>n>>nri;

    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
        a[i][j]=inf;

    for(i=1;i<=nri;i++)
    {   fin>>x>>y>>c;
        a[x][y]=a[y][x]=c;}

for(i=1;i<=n;i++)
        d[i]=inf;
    d[1]=0;m[1]=1;
push(1);

while(!hempty())
{
vf=top();
m[vf]=1;
for(i=1;i<=n;i++)
    if(!m[i] && d[i]>d[vf]+a[vf][i])
  {d[i]=d[vf]+a[vf][i];
    push(i);}
}

    for(i=2;i<=n;i++)
        fout<<d[i]<<' ';
}