#include<fstream>
#include<iostream>

using namespace std;

int a[25][25],n,m,d[25];

void citire()
{
    ifstream f("dijkstra.in");
    f>>n>>m;
    for(int i=1;i<=n;i++)
    {
        int x, y, z;
        f>>x>>y>>z;
        a[x][y]=z;
        for(int j=1;j<=n;j++)if(a[i][j]==0) a[i][j]=9999;
    }
    f.close();
}

void dij(int n,int v,int cost[25][25],int dist[])
{
 int i,u,count,w,flag[10],min;
 for(i=1;i<=n;i++)
  flag[i]=0,dist[i]=cost[v][i];
 count=2;
 while(count<=n)
 {
  min=99;
  for(w=1;w<=n;w++)
   if(dist[w]<min && !flag[w])
    min=dist[w],u=w;
  flag[u]=1;
  count++;
  for(w=1;w<=n;w++)
   if((dist[u]+cost[u][w]<dist[w]) && !flag[w])
    dist[w]=dist[u]+cost[u][w];
 }
}

int main()
{
    citire();
    dij(n,1,a,d);
    ofstream g("dijkstra.out");
    for(int i=2;i<=n;i++)
        g<<d[i]<<' ';
        g.close();
    return 0;
}