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

using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
int n, m;
int dist[50001];
vector<edge> graf[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(y, z));
}

void solve()
{
  for(int i = 2;i <= n;++i)
    dist[i] = oo;

  set<pair<int, int>> heap;
  heap.insert(make_pair(0, 1));

  while(!heap.empty())
  {
    int nod = heap.begin() -> second;
    heap.erase(heap.begin());

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

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