#include<bits/stdc++.h>
using namespace std;
priority_queue<pair<int, int>> q;
vector<int> odl(100007, INT_MAX);
vector<pair<int, int>> G[100007];
int main(){
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int n, m, v, dist;
  cin >> n >> m;
  for(int i = 0, a, b, c;i < m;i++){
    cin >> a >> b >> c;
    G[b].emplace_back(a, c);
  }
  q.emplace(0ll, 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] == INT_MAX)
      cout << "+oo\n";
    else
      cout << odl[i] << '\n';
  }
}