#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <utility>

using namespace std;

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

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

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

 fin>>n>>m;

 dist[1]=0;
 heap.push(make_pair(-dist[1],1));
 for(i=2;i<=n;i++)
     {
      dist[i]=800000000;
      heap.push(make_pair(-dist[i],i));
     }

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


 while(!heap.empty())
 {
  pair <int,int> best=heap.top();

  index=best.second;
  heap.pop();

  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];
       heap.push(make_pair(-dist[vecin],vecin));
      }

  }

  viz[index]=1;

 }

 for(i=2;i<=n;i++)
    if(dist[i]==800000000) fout<<"0 ";
    else  fout<<dist[i]<<" ";


    return 0;
}