#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

vector <int> a[50001],c[50001];
int dist[50001],viz[50001];

int main()
{
 int i,n,m,x,y,z,k,index,min,vecin,cost;

 fin>>n>>m;
 for(i=1;i<=m;i++)
 {
  fin>>x>>y>>z;
  a[x].push_back(y);
  c[x].push_back(z);
 }

 dist[1]=0;
 for(i=2;i<=n;i++)
    dist[i]=30000;

 for(k=1;k<=n;k++)
 {
  min=30000;

  for(i=1;i<=n;i++)
     if(min>dist[i] && viz[i]==0)
       {
        index=i;
        min=dist[i];
       }

  for(i=0;i<a[index].size();i++)
  {
   vecin=a[index][i];
   cost=c[index][i];

   if(dist[vecin]>cost+dist[index])
      dist[vecin]=cost+dist[index];

  }

  viz[index]=1;

 }

 for(i=2;i<=n;i++)
    fout<<dist[i]<<" ";


    return 0;
}