#include<bits/stdc++.h>
using namespace std;
int main(){
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int n, m, v;
  long long dist;
  cin >> n >> m;
  vector<pair<int, int>> G[n + 1];
  vector<long long> odl(n + 1, LLONG_MAX);
  for(int i = 0, a, b, c;i < m;i++){
    cin >> a >> b >> c;
    G[b].emplace_back(a, c);
  }
  priority_queue<pair<long long, int>> q;
  q.emplace(0, 1);
  while(!q.empty()){
    tie(dist, v) = q.top();
    q.pop();
    if(-dist > odl[v])
      continue;
    odl[v] = -dist;
    for(auto i : G[v])
      if(odl[i.first] > -dist + i.second)
        q.emplace(dist - i.second, i.first);
  }
  for(int i = 1;i <= n;i++){
    if(odl[i] == LLONG_MAX)
      cout << "+oo\n";
    else
      cout << odl[i] << '\n';
  }
}