#include<fstream>
#define INF 1<<31;
using namespace std;

int x,y,c,n,m,vis[50000],dist[50000];
int con[5000][5000];
int main()
{
  ifstream f("dijkstra.in");
  ofstream g("dijkstra.out");

  f>>n>>m;

  for(int i=0;i<m;i++)
    f>>x>>y>>c, con[x][y]=c;

  for(int i=0;i<n;i++)
  {
    dist[i] = INF;
    vis[i] = 0;
  }
  
  dist[0] = 0;
  

  int nn=0;
  while(nn<=n)
  {
    int minI, min = INF;
    for(int j=0;j<n;j++)
    {
      if(dist[j]<min && !vis[j])
      {
        min = dist[j];
        minI = j;
      }
    }

    vis[minI] = 1;

    for(int i=0;i<n;i++)
      if(dist[minI] + con[minI][i] < dist[i])
        dist[i] = dist[minI] + con[minI][i];
    nn++;
  }

  for(int i=1;i<n;i++)
    g<<dist[i]<<" ";

  f.close();
  g.close();   
}