#include <iostream>
#include<fstream>
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
int a[101][101],c,n,i,j,p,x,y,z,m;
int d[101],s[101],t[101],minim,poz,Max=1000000;
int main()
{ f>>n>>m;
p=1;
  for(i=1;i<=n;i++)
    for(j=1;j<=n;j++)
    if(i==j) a[i][j]=0;
  else a[i][j]=Max;
  for(i=1;i<=m;i++)
  {
      f>>x>>y>>z;
      a[x][y]=z;
  }

    //initializez vectorii d,s,t
    s[p]=1;
    for(i=1;i<=n;i++)
    {
        d[i]=a[p][i];
        if(i!=p)
            if(d[i]<Max) t[i]=p;
    }
    //prelucrez vectorii d,s,t
    for(i=1;i<=n-1;i++)
    {
        minim=Max;
        for(j=1;j<=n;j++)
            if(s[j]==0)
            if(d[j]<minim) minim=d[j],poz=j;
    s[poz]=1;
    for(j=1;j<=n;j++)
        if(s[j]==0)
          if(d[j]>d[poz]+a[poz][j])
    {
        d[j]=d[poz]+a[poz][j];
        t[j]=poz;
    }
    }
    for(i=2;i<=n;i++)
        if(d[i]<Max)
        g<<d[i]<<" ";
    else g<<-1<<" ";

    return 0;
}