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

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

void read()
{
  f>>n>>m;
  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<point> heap;
  heap.insert(make_pair(0, 1));

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

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

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