#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define mii map <int, int>
#define mll map <ll, ll>
#define pii pair <int, int>
#define pll pair <ll, ll>
#define vi vector <int>
#define vd vector <double>
#define vll vector <ll>
#define fi first
#define se second
#define si set <int>
#define sll set <ll>
#define spii set <pii>
#define vs vector <string>
#define vpii vector <pair <int, int> >
#define vpll vector <pair <long long, long long> >
#define vvi vector <vector <int> >
#define vvpii vector <vector <pii > >
#define vb vector <bool>
#define vvb vector <vb>
#define mp make_pair
#define vvll vector <vll>
#define vsi vector <si>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define MANX MAXN
#define itn int
#define dbg(x); {cout << #x << "=" << x << ", ";}
#define in(x); { for (auto &to : x) cin >> to;}
#define out(x); { for (auto &to : x) cout << to << " "; cout << '\n'; }

const ll INFLL = 1e18;
const int MAXN = 1e6+100;
const ll INF = 1e9;
const int mod1 = 1e9+7;
const int mod2 = 1e9+21;

void solve()
{
    int n,m;
    cin>>n>>m;
    vector <vpii> g(n);
    while (m--)
    {
        int a,b,c;
        cin>>a>>b>>c;
        a--,b--;
        g[a].pb({b,c});
    }
    for (int st=0;st<n;st++)
    {
        vi d(n,2*INF);
        set<pii> s;
        s.insert({0,st});
        while (!s.empty())
        {
            auto to=s.begin();
            pii f=*to;
            s.erase(to);
            for (auto too:g[f.se])
            {
                if (d[too.fi]>f.fi+too.se)
                {
                    s.erase({d[too.fi],too.fi});
                    d[too.fi]=f.fi+too.se;
                    s.insert({d[too.fi],too.fi});
                }
            }
        }
        cout<<(d[st]==2*INF?-1:d[st])<<'\n';
    }
}

int main() {
    #ifdef Mip182
    freopen("a.in", "r", stdin);
    #else
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    #endif
    int _t;
    _t=1;
//    cin>>_t;
    while (_t--)
        solve();
    #ifdef Mip182
    cout<<'\n'<<"Time : "<<(double)(clock())/CLOCKS_PER_SEC<<'\n';
    #endif
}

#pragma GCC optimize ("O2")
#pragma GCC target ("avx2")
//#include<bits/stdc++.h>
//#include<atcoder/all>
//using namespace atcoder;
#include<cstdio>
#include<queue>

using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout << (x) << " "
#define ce(x) cerr << (x) << "\n"
#define cesp(x) cerr << (x) << " "
#define pb push_back
#define mp make_pair
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
#define Would
#define you
#define please

char c;
inline int getint() {
	int ret = 0;
	while ((c = getchar_unlocked()) >= '0') ret = ret * 10 + c - '0';
	return ret;
}
int to[2001], ne[2001], co[2001], he[2001];

const int AS = 2020;
class saishou_tekitou_heap {
public:
	int HS = 0;
	const ll IM = 2e18;
	ll dat[AS * 2 + 2];
	saishou_tekitou_heap() : dat() {
		dat[0] = -IM;
		rep1(i, AS * 2 + 1) dat[i] = IM;
	}
	void push(ll v) {
		int p = ++HS;
		while (v < dat[p >> 1]) dat[p] = dat[p >> 1], p >>= 1;
		dat[p] = v;
	}
	ll pop() {
		if (HS == 1) {
			HS = 0;
			return dat[1];
		}
		ll ret = dat[1];
		ll v = dat[HS];
		dat[HS--] = IM;
		int j = 2 + (dat[2] > dat[3]);
		while (v > dat[j]) {
			dat[j >> 1] = dat[j];
			j <<= 1;
			j += dat[j] > dat[j + 1];
		}
		dat[j >> 1] = v;
		return ret;
	}
} PQ;
int main() {
	//cin.tie(0);
	//ios::sync_with_stdio(false);


	int N = getint(), M = getint();

	rep1(i, M) {
		int a = getint();
		to[i] = getint();
		co[i] = getint();
		ne[i] = he[a];
		he[a] = i;
	}

	ll D[2001] = {};
	ll b = 1000000000ll * N;
	const ll ma = (1 << 16) - 1;
	rep1(i, N) D[i] = b;
	rep1(n, N) {
		b -= 1000000000ll;

		D[n] = b;
		PQ.push(b << 16 | n);
		ll saishou = 1e18;
		while (PQ.HS) {
			ll p = PQ.pop();
			int i = p & ma;
			ll d = p >> 16;
			if (D[i] != d) continue;
			for (int t = he[i]; t; t = ne[t]) {
				int j = to[t];
				ll d2 = d + co[t];
				if (j == n) {
					chmin(saishou, d2);
				}
				if (D[j] > d2) {
					D[j] = d2;
					PQ.push(d2 << 16 | j);
				}
			}
		}

		if (saishou > 1e17) printf("-1\n");
		else printf("%d\n", saishou - b);
	}

	Would you please return 0;
}