#include<bits/stdc++.h>
#define ll long long int
#define M 1000000007
#define mod 998244353
#define mp(x,y) make_pair(x,y)
#define pb(x) push_back(x)
#define pi pair<ll,ll>
#define endl "\n"
using namespace std;
const ll N=100010;

vector<pi> adj[N];

vector<vector<ll> > dis;

void func(ll start)
{
    set<pi> s;
    s.insert(mp(0,start));
    int firstdone=0;
    while(!s.empty()){
        ll v=(*s.begin()).second;
        ll d=(*s.begin()).first;
        s.erase(s.begin());
        if(dis[start][v]<=d){continue;}
        if(v==start){
            if(firstdone==0){
                firstdone=1;
            }
            else{
                dis[start][v]=d;
            }
        }
        else{
            dis[start][v]=d;
        }
        for(auto x:adj[v]){
            ll u=x.first,w=x.second;
            if(dis[start][u]>d+w){
                s.insert(mp(d+w,u));
            }
        }
    }
}

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

    ll n,m;
    cin>>n>>m;
    for(ll i=0;i<m;++i){
        ll a,b,w;
        cin>>a>>b>>w;
        adj[a].pb(mp(b,w));
    }

    dis.resize(n+1,vector<ll>(n+1,INT_MAX));

    for(ll i=1;i<=n;++i){
        func(i);
    }

    for(ll i=1;i<=n;++i){
        if(dis[i][i]==INT_MAX){
            dis[i][i]=-1;
        }
        cout<<dis[i][i]<<endl;
    }

    return 0;
}

#include <bits/stdc++.h>
//#include <chrono>
//#pragma GCC optimize("Ofast")
using namespace std;
#define reps(i,s,n) for(int i = s; i < n; i++)
#define rep(i,n) reps(i,0,n)
#define Rreps(i,n,e) for(int i = n - 1; i >= e; --i)
#define Rrep(i,n) Rreps(i,n,0)
#define ALL(a) a.begin(), a.end()

using ll = long long;
using vec = vector<ll>;
using mat = vector<vec>;

ll N,M,H,W,Q,K,A,B;
string S;
using P = pair<ll, ll>;
const ll INF = (1LL<<60);

template<class T> bool chmin(T &a, const T b){
    if(a > b) {a = b; return true;}
    else return false;
}
template<class T> bool chmax(T &a, const T b){
    if(a < b) {a = b; return true;}
    else return false;
}
template<class T> void my_printv(std::vector<T> v,bool endline = true){
    if(!v.empty()){
        for(std::size_t i{}; i<v.size()-1; ++i) std::cout<<v[i]<<" ";
        std::cout<<v.back();
    }
    if(endline) std::cout<<std::endl;
}

struct edge{
        int to;
        ll cost;
        edge(){}
        edge(int a, ll b) : to(a), cost(b){}
    };

using ve = vector<edge>;

void dijkstra(int s, vec &dist, vector<ve> &G){
    priority_queue<P, vector<P>, greater<> > pque;
    for(edge &e : G[s]){
        if(chmin(dist[e.to], e.cost)){
            pque.emplace(dist[e.to], e.to);
        }
    }
    while(!pque.empty()){
        P p = pque.top(); pque.pop();
        int v = p.second;
        if(dist[v] < p.first) continue;
        for(const edge &e : G[v]){
            if(chmin(dist[e.to], dist[v] + e.cost)){
                pque.emplace(dist[e.to], e.to);
            }
        }
    }
}

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cin>>N>>M;
    vector<ve> G(N);
    rep(i, M){
        int a, b;
        ll c;
        cin>>a>>b>>c;
        --a; --b;
        G[a].emplace_back(b, c);
    }
    rep(i, N){
        vec dist(N, INF);
        dijkstra(i, dist, G);
        cout<<(dist[i] == INF ? -1 : dist[i])<<endl;
    }
}