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

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

void solve()
{
  for(int i = 2;i <= n;++i)
    dist[i] = oo;
  set<pair<int, int>> h;
  dist[1] = 0;

  h.insert(make_pair(0, 1));

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

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

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));
} 

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