#include <fstream>
#include <vector>
#include <queue>
#include <list>
#include <set>

#define intPair pair<int, int>

using namespace std;

ifstream cin("dijkstra.in");
ofstream cout("dijkstra.out");

int n, e;
list<pair<int, int>> v[50002];
int x, y, w;

void dijkstra(int src);

int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  cin >> n >> e;
  for(int i = 1; i <= e; i++)
  {
    cin >> x >> y >> w;
    v[x].push_back({y, w});
  }
  dijkstra(1);
  return 0;
}

void dijkstra(int src)
{
  vector<int> dist(n + 1, 1e9);
  //priority_queue<intPair, vector<intPair>, greater<intPair>> pq;
  set<intPair> st;
  //pq.push({0, src});
  st.insert({0, src});
  dist[src] = 0;
  while(/*!pq.empty()*/ !st.empty())
  {
    //int crt_node = pq.top().second;
    //pq.pop();
    int crt_node = st.begin()->second;
    st.erase(st.begin());
    for(auto link : v[crt_node])
    {
      int next_node = link.first;
      int weight = link.second;
      if(dist[next_node] > dist[crt_node] + weight)
      {
        if(dist[next_node] != 1e9)
          st.erase(st.find({dist[next_node], next_node}));
        dist[next_node] = dist[crt_node] + weight;
        //pq.push({dist[next_node], next_node});
        st.insert({dist[next_node], next_node});
      }
    }
  }
  for(int i = 2; i <= n; i++)
  {
    if(dist[i] == 1e9)
      dist[i] = 0;
    cout << dist[i] << ' ';
  }
  cout << '\n';
  return ;
}