// ----- In the name of ALLAH, the Most Gracious, the Most Merciful -----

#include<bits/stdc++.h>
using namespace std;

#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
  enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
  ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
  *this << "[";
  for (auto it = d.b; it != d.e; ++it)
    *this << ", " + 2 * (it == d.b) << *it;
  ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define deb(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
#define int long long
#define endl "\n"
#define mod 1000000007
#define inf (int)1e18

const int mxn = 2e3+5;
vector<pair<int,int>> g[mxn];
bool vis[mxn];
int d[mxn];

int32_t main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int n,m; cin >> n >> m;
    for(int i=0;i<m;i++){
        int u,v,c; cin >> u >> v >> c;
        g[v].push_back({u,c});
        // g[u].push_back({v,c});
    }

    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            d[j] = inf;
            vis[j] = false;
        }
        d[i] = inf;
        priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> q;
        q.push({0,i});

        while(!q.empty()){
            int c = q.top().first;
            int v = q.top().second;
            q.pop();

            for(auto it : g[v]){
                int u = it.first;
                int cost = it.second;

                if(d[u]> cost+c){
                    d[u] = cost + c;
                    vis[u] = 1;
                    q.push({d[u],u});
                }
            }
        }

        if(d[i]==inf) cout << -1 << endl;
        else cout << d[i] << endl;
    }
    
    return 0;
}
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG
#define rep(i, from, to) for (ll i = from; i < (to); ++i)
#define mp(x,y) make_pair(x,y)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
#define pb push_back
using ll = long long;
using ld=long double;
using vin=vector<int>;
using vvin=vector<vin>;
using vll=vector<ll>;
using vvll=vector<vll>;
using vst=vector<string>;
using P = pair<ll,ll>;
using vp=vector<P>;
using vvp=vector<vp>;
const int inf=1e9+7;
const ll INF=9e18/2;
const long double PI = acos(-1.0); 
template <typename T> bool chmin(T &a, const T& b){if(a > b){a = b;return true;}return false;}
template <typename T> bool chmax(T &a, const T& b){if(a < b){a = b;return true;}return false;}
template<class T> inline void Yes(T condition){ if(condition) cout << "Yes" << endl; else cout << "No" << endl; }
template<class T> inline void YES(T condition){ if(condition) cout << "YES" << endl; else cout << "NO" << endl; }
const int dx[4] = { 0, 0, 1, 1 };
const int dy[4] = { 0, 1, 0, 1 };


template<class T>
struct dijkstra{
  struct edge{
    int to;
    T cost;
  };

  vector<T> dist;
  vector<int> prev;
  vector<vector<edge>> g;
  T Inf;

  dijkstra(int n,T _Inf):Inf(_Inf){
   init(n);
   g.resize(n);
  };

  void init(int n){
   prev.assign(n,-1);
   dist.assign(n,Inf);
  }

  void add_edge(int s,int t,T cost){
   g[s].push_back((edge){t,cost});
  }

  void run(int s){
    priority_queue<pair<T,int>,vector<pair<T,int>>,greater<pair<T,int>>> pq;
    dist[s]=0;
    pq.push(pair<T,int>(0,s));
    while(!pq.empty()){
      int now=pq.top().second;
      T now_cost=pq.top().first;
      pq.pop();
      if(dist[now]<now_cost)continue;
      for(auto v:g[now]){
        if(dist[v.to]>dist[now]+v.cost){
          dist[v.to]=dist[now]+v.cost;
          prev[v.to]=now;
          pq.push(pair<T,int>(dist[v.to],v.to));
        }
      }
    }
  }
};

int main(){//cout<<fixed<<setprecision(20);
  int n,m;
  cin>>n>>m;
  dijkstra<ll> dijk(2*n,INF);
  rep(i,0,m){
    ll a,b,c;
    cin>>a>>b>>c;
    a--;b--;
    b+=n;
    dijk.add_edge(a,b,c);
    a+=n;
    dijk.add_edge(a,b,c);
  }
  rep(i,0,n){
   dijk.run(i);
   ll ans=INF;
   chmin(ans,dijk.dist[i+n]);
   dijk.init(n*2);
    if(ans==INF)ans=-1;
   cout<<ans<<endl;
  }
}