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

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

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

void solve()
{
  for(int i = 2;i <= n;++i)
    dist[i] = oo;
  dist[1] = 0;
  set<edge> heap;
  heap.insert(make_pair(0, 1));

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

    for(auto it : graph[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[it.node], it.node));
      }
  }

  for(int i = 2;i <= n;++i)
    g<<(dist[i] == oo ? 0 : dist[i])<<" ";
}

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