#include <bits/stdc++.h>
using namespace std;
ifstream in("dijkstra.in");
ofstream out("dijkstra.out");
int n,m;
vector < pair <int,int> > g[50001];
int d[50001];
priority_queue < pair <int,int> > h;
void dijkstra(int nod)
{  for(int i=1;i<=n;i++)
    d[i]=1<<30;
  d[nod]=0;
  h.push(make_pair(0,nod));
  while(!h.empty())
  { int node=h.top().second;
    int cost=-h.top().first;
    h.pop();
    if(d[node]!=1<<30 && d[node]!=0)
       continue;
    d[node]=cost;
    for(auto it: g[node])
      if(d[it.first]>cost+it.second)
         h.push(make_pair(-cost-it.second,it.first));

  }
}
int main()
{ in>>n>>m;
  for(int i=1;i<=m;i++)
  { int x,y,c;
    in>>x>>y>>c;
    g[x].push_back(make_pair(y,c));
  }
  dijkstra(1);
  for(int i=2;i<=n;i++)
    if(d[i]==1<<30)
       out<<"0 ";
    else
       out<<d[i]<<" ";
  out<<'\n';
  in.close();
  out.close();
  return 0;
}