#include <iostream>
#include <vector>
#include <queue>
#include <climits>
 
FILE * fin = fopen("dijkstra.in","r");
FILE * fout= fopen("dijkstra.out","w");
 
struct edge
{
  int x, w;
};
struct nod
{
  int x, d;
};
struct Comp: std::binary_function<nod,nod,bool>
{
  bool operator() (nod n1, nod n2)
  {
    if(n1.d!=n2.d)
      return n1.d>n2.d;
    return n1.x>n2.x;
  }
};
 
int n,m;
std::priority_queue<nod,std::vector<nod>,Comp> pq;
std::vector<edge> v[50050];
int dist[50050];
bool vis[50050];
 
int main()
{
  fscanf(fin,"%d %d",&n,&m);
  for(int i=0;i<m;i++)
  {
    int j,k,o;
    fscanf(fin,"%d %d %d",&j,&k,&o);
    v[j].push_back({k,o});
  }
  for(int i=1;i<=n;i++)
    dist[i]=INT_MAX;
  dist[1]=0;
  nod root = {1,0};
  pq.push(root);
  while(!pq.empty())
  {
    nod tp = pq.top();
  //  std::cout<<tp.x<<" ";
    pq.pop();
    if(vis[tp.x])continue;
    vis[tp.x]=true;
    for(int i=0;i<v[tp.x].size();i++)
    {
      edge elem = v[tp.x][i];
      if(elem.w+tp.d<dist[elem.x])
      {
        dist[elem.x]=elem.w+tp.d;
        pq.push({elem.x,dist[elem.x]});
      }
    }
  }
  for(int i=2;i<=n;i++)
  {
    if(dist[i]==INT_MAX)
      fprintf(fout,"0 ");
    else
      fprintf(fout,"%d ",dist[i]);
  }//*/
}