#include <bits/stdc++.h>
using namespace std;
int n,m;
int dist[2010][2010];
int dp[2010][2010];
vector<int> v[2010];
int main()
{
	cin>>n>>m;
	for(int i=0;i<m;i++)
	{
		int x,y,z;
		cin>>x>>y>>z;
		if(!dist[x][y]||dist[x][y]>z)
		dist[x][y]=z;
	}
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			if(dist[i][j])
				v[i].push_back(j);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			dp[i][j]=1e9;
	for(int i=1;i<=n;i++)
	{
		dp[i][i]=0;
		queue<int> q;
		q.push(i);
		while(!q.empty())
		{
			int x=q.front();
			q.pop();
			for(int j=0;j<v[x].size();j++)
				if(dp[i][v[x][j]]>dp[i][x]+dist[x][v[x][j]])
				{
					dp[i][v[x][j]]=dp[i][x]+dist[x][v[x][j]];
					q.push(v[x][j]);
				}
		}
	}
	for(int i=1;i<=n;i++)
	{
		int ans=1e9;
		for(int j=1;j<=n;j++)if(dist[j][i])ans=min(ans,dist[j][i]+dp[i][j]);
		if(ans==1e9)cout<<-1<<endl;
		else cout<<ans<<endl;
	}
	return 0;
}
#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false); cin.tie(0);
#define FOR(i,s,n) for(int i = (s); i < (n); i++)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) for(int i = (n); i >= 0; i--)
#define ALL(n) (n).begin(), (n).end()
#define RALL(n) (n).rbegin(), (n).rend()
#define ATYN(n) cout << ( (n) ? "Yes":"No") << '\n';
#define CFYN(n) cout << ( (n) ? "YES":"NO") << '\n';
#define OUT(n) cout << (n) << '\n';
using ll = long long;
using ull = unsigned long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;


int main(void)
{
    IOS
    const int INF = 1e9;
    int n, m;
    cin >> n >> m;
    vector<vector<pii>> v(n);
    vector<int> self(n,INF);
    REP(i,m) {
        int a, b, c;
        cin >> a >> b >> c;
        a--; b--;
        if (a == b) self[a] = min(self[a],c);
        else v[a].emplace_back(c,b);
    }

    auto dijkstraToAll = [&](const int from) {
        priority_queue<pii,vector<pii>,greater<pii>> pq;
        vector<bool> visit(n);
        vector<int> ret(n,INF);
        for (auto p : v[from]) pq.push(p);
        visit[from] = true;
        while(!pq.empty()) {
            pii p = pq.top();
            pq.pop();
            if (visit[p.second]) continue;
            visit[p.second] = true;
            ret[p.second] = p.first;
            for(auto [c,b]:v[p.second]) {
                if (!visit[b]) pq.push({p.first+c,b});
            }
        }
        return ret;
    };

    vector<vector<int>> len;
    REP(i,n) len.push_back(dijkstraToAll(i));
    REP(i,n) {
        int ans = self[i];
        REP(j,n) ans = min(ans,len[i][j]+len[j][i]);
        if (ans <INF) OUT(ans)
        else OUT(-1)
    }

    return 0;
}