#include<bits/stdc++.h>
using namespace std;
template <typename T> T getczary(){//magia!
  int ujemna = false, znak = getchar_unlocked();
  T wynik = (T)0;
  while(!isdigit(znak)){
    if(znak == '-')
      ujemna = true;
    znak = getchar_unlocked();
  }
  while(isdigit(znak)){
    wynik *= 10;
    wynik += znak - '0';
    znak = getchar_unlocked();
  }
  if(ujemna)
    wynik *= -1;
  return wynik;
}
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;
  n = getczary<int>();
  m = getczary<int>();
  for(int i = 0, a, b, c;i < m;i++){
    a = getczary<int>();
    b = getczary<int>();
    c = getczary<int>();
    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 << odl[i] << '\n';
    else
      cout << "+oo\n";
  }
}