#include <bits/stdc++.h>

using namespace std;

#define MAX 1e9

int main(){
    int n,m,a,b,c;
    pair<int,int> x;
    cin>>n>>m;
    vector<pair<int,int>> lst[n];
    for(int i=0; i<m; i++){
        cin>>a>>b>>c;
        lst[a-1].push_back({-c,b-1});
    }

    bool visited[n],exists;
    for(int i=0; i<n; i++){
        priority_queue<pair<int,int>> pr;
        
        memset(visited,false,n);
        for(int j=0; j<lst[i].size(); j++) pr.push(lst[i][j]);
        
        exists=false;
        while(!pr.empty()){
            if(pr.top().second==i){
                exists=true;
                break;
            }
            x=pr.top();
            //cout<<x.second<<" ";
            pr.pop();
            if(visited[x.second])continue;
            else visited[x.second]=true;
            for(int j=0; j<lst[x.second].size(); j++) pr.push({x.first+lst[x.second][j].first,lst[x.second][j].second}); 
        }

        if(exists)cout<<(-pr.top().first)<<"\n";
        else cout<<"-1\n";
        //cout<<endl;
    }
}
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>

using namespace std;

using i64 = long long;
#define forn(a, e) for (i64 a = 0; a < (i64)(e); a++)
#define forr(a, s, e) for (i64 a = s; a < (i64)(e); a++)
#define fore(e, a) for (auto& e : a)

#ifdef LOCAL
#define logv(a) {cerr << #a << " = "; fore(e, a) {cerr << e << " ";} cerr << "\n";}
#define logvp(a) {cerr << #a << " = "; fore(e, a) {cerr << "(" << e.first << ", " << e.second << ") ";} cerr << "\n";}
#define logvv(a) {cerr << #a << " = \n"; fore(r, a) { fore(e, r) {cerr << e << " ";} cerr << "\n";} }
#define logvf(a, field) {cerr << #a"."#field << " = \n"; fore(e, a) { cerr << e.field << " ";} cerr << "\n"; }
#define logvff(a, f1, f2) {cerr << #a".{"#f1 << ", "#f2 << "} = \n"; fore(e, a) { cerr << "(" << e.f1 <<", " << e.f2 << ") ";} cerr << "\n"; }
#define logs(a) cerr << #a << " = " << (a) << "\n";
#define logss(a, b) cerr << #a << " = " << (a) << ", " << #b << " = " << (b) << "\n";
#define logp(a) cerr << #a << " = " << "(" << a.first << ", " << a.second << ")" << "\n";
#define cond(pred, stmt) if (pred) { stmt }
#else
#define logv(a)
#define logvp(a)
#define logvv(a)
#define logvf(a, field)
#define logvff(a, f1, f2)
#define logs(a)
#define logss(a, b)
#define logp(a)
#define cond(pred, stmt)
#endif

using iip = pair<int, int>;
using llp = pair<i64, i64>;
using ivec = vector<int>;
using llvec = vector<i64>;
using svec = vector<string>;
template<typename T> using vec = vector<T>;

template<typename T, typename Dim>
auto make_vec(T value, Dim dim) { return vector<T>(dim, value); }
template<typename T, typename Dim1, typename... Dim>
auto make_vec(T value, Dim1 dim1, Dim... dims) { return make_vec(make_vec(value, dims...), dim1); }

template<typename T>
bool uax(T& v, const T& newv) { if (v < newv) { v = newv; return true; } else return false; }
template<typename T>
bool uin(T& v, const T& newv) { if (v > newv) { v = newv; return true; } else return false; }

template<typename T>
istream& operator>>(istream& is, vector<T>& c) { for (auto& e : c) is >> e; return is; }
template<typename T, size_t N>
istream& operator>>(istream& is, array<T, N>& c) { for (auto& e : c) is >> e; return is; }

template<typename ...T>
istream& read(T&... args) { return (cin >> ... >> args); }

static mt19937 rande(123123);
template<typename T>
T rand_int(T from, T to) { uniform_int_distribution<T> distr(from, to); return distr(rande); }

// const i64 INF = 2e18;
const int INF = 2e9;
const __int128_t M = 1000000;
const int MXB = 20;
using bin = bitset<MXB + 1>;
const double EPS = 1e-8;


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    rande.seed(chrono::steady_clock::now().time_since_epoch().count());

    int n, m;
    while (read(n, m)) {
        vec<vec<iip>> g(n);
        vec<vec<iip>> ing(n);

        forn(i, m) {
            int a, b, c;
            read(a, b, c);
            a--; b--;
            g[a].emplace_back(b, c);
            ing[b].emplace_back(a, c);
        }

        auto check_city = [&](int s) {
            int ans = 1e9;

            priority_queue<iip, vec<iip>, greater<iip>> q;
            ivec dist(n, 1e9);
            dist[s] = 0;
            q.emplace(0, s);

            while (!q.empty()) {
                auto [d, v] = q.top();
                q.pop();

                if (d != dist[v]) {
                    continue;
                }

                for (auto [u, w] : g[v]) {
                    if (uin(dist[u], dist[v] + w)) {
                        q.emplace(dist[u], u);
                    }
                }
            }

            for (auto [v, w] : ing[s]) {
                uin(ans, dist[v] + w);
            }

            return ans;
        };

        ivec ans(n);
        forn(i, n) {
            ans[i] = check_city(i);
            if (ans[i] == 1e9) {
                ans[i] = -1;
            }
        }

        forn(i, n) {
            cout << ans[i] << "\n";
        }
    }
}