#include <bits/stdc++.h>
#define oo 0x3f3f3f3f
#define edge pair<int, int>
#define cost first
#define node second

using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
int n, m;
vector<edge> graf[50001];
int dist[50001];

void read()
{
  f>>n>>m;
  int x, y, z;
  for(int i = 1;i <= m;++i)
    f>>x>>y>>z, graf[x].push_back(make_pair(z, y));
}

void solve()
{
  memset(dist, oo, sizeof(dist));
  dist[1] = 0;
  set<edge> heap;
  heap.insert(make_pair(0, 1));

  while(!heap.empty())
  {
    int node_f = heap.begin() -> node;
    heap.erase(heap.begin());
    
    for(auto it : graf[node_f])
      if(dist[it.node] > dist[node_f] + it.cost)
      {
        if(dist[it.node] != oo)
          heap.erase(heap.find(make_pair(dist[it.node], it.node)));
        
        dist[it.node] = dist[node_f] + it.cost;
        heap.insert(make_pair(dist[it.node], it.node));
      } 
  }
  for(int i = 2;i <= n;++i)
    g<<(dist[i] != oo ? dist[i] : 0)<<' ';
}

int main()
{
  read();
  solve();
  return 0;
}