#include <bits/stdc++.h>
using namespace std;
using ll = long long;
// --------------------------------------------------------
template<class T> bool chmax(T& a, const T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> bool chmin(T& a, const T b) { if (b < a) { a = b; return 1; } return 0; }
#define FOR(i,l,r) for (ll i = (l); i < (r); ++i)
#define RFOR(i,l,r) for (ll i = (r)-1; (l) <= i; --i)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define ALL(c) (c).begin(), (c).end()
#define RALL(c) (c).rbegin(), (c).rend()
#define SORT(c) sort(ALL(c))
#define RSORT(c) sort(RALL(c))
#define MIN(c) *min_element(ALL(c))
#define MAX(c) *max_element(ALL(c))
#define SUMLL(c) accumulate(ALL(c), 0LL)
#define SZ(c) ((ll)(c).size())
#define BIT(b,i) ((b>>i) & 1)
#define PCNT(b) __builtin_popcountll(b)
#define CIN(c) cin >> (c)
#define COUT(c) cout << (c) << '\n'
#define debug(x) cerr << "l." << __LINE__ << " : " << #x << " = " << (x) << '\n'
ll llceil(ll a, ll b) { return (a + b - 1) / b; }
string toupper(const string& S) { string T(S); REP(i,SZ(T)) T[i] = toupper(T[i]); return T; }
string tolower(const string& S) { string T(S); REP(i,SZ(T)) T[i] = tolower(T[i]); return T; }
using P = pair<ll,ll>;
using VP = vector<P>;
using VVP = vector<VP>;
using VS = vector<string>;
using VVS = vector<VS>;
using VLL = vector<ll>;
using VVLL = vector<VLL>;
using VVVLL = vector<VVLL>;
using VB = vector<bool>;
using VVB = vector<VB>;
using VVVB = vector<VVB>;
using VD = vector<double>;
using VVD = vector<VD>;
using VVVD = vector<VVD>;
static const double EPS = 1e-10;
static const double PI  = acos(-1.0);
static const ll MOD = 1000000007;
// static const ll MOD = 998244353;
static const ll INF = (1LL << 62) - 1;  // 4611686018427387904 - 1
// --------------------------------------------------------
// #include <atcoder/all>
// using namespace atcoder;


int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(15);

    ll N, M; cin >> N >> M;
    VLL ans(N,INF);

    VVLL H(N,VLL(N,INF));
    REP(_,M) {
        ll A, B, C; cin >> A >> B >> C;
        A--; B--;
        if (A == B) {
            chmin(ans[A], C);
        } else {
            chmin(H[A][B], C);
        }
    }

    VVP G(N);
    REP(i,N) REP(j,N) if (H[i][j] != INF) G[i].push_back(P(H[i][j],j));
    VLL dist(N);
    queue<P> q;
    REP(s,N) {
        REP(i,N) dist[i] = INF;
        dist[s] = 0; q.push(P(0, s));
        while (!q.empty()) {
            auto [min_dist, u] = q.front(); q.pop();
            if (dist[u] < min_dist) continue;
            for (auto [c, v] : G[u]) {
                if (v == s) {
                    chmin(ans[s], dist[u] + c);
                } else {
                    if (chmin(dist[v], dist[u] + c)) {
                        q.push(P(dist[v], v));
                    }
                }
            }
        }
    }

    REP(i,N) if (ans[i] == INF) ans[i] = -1;
    REP(i,N) COUT(ans[i]);

    return 0;
}

#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define fun function
#define sz(x) (int)(x).size()
#define lowbit(x) (x)&(-x)
#define all(x) (x).begin(),(x).end()
#define mem(a,b) memset(a,b,sizeof(a))

namespace FastIO {
#define BUF_SIZE 100000
#define OUT_SIZE 100000
    bool IOerror=0;
    inline char nc() {
        static char buf[BUF_SIZE],*p1=buf+BUF_SIZE,*pend=buf+BUF_SIZE;
        if(p1==pend) {
            p1=buf;
            pend=buf+fread(buf,1,BUF_SIZE,stdin);
            if(pend==p1) {
                IOerror=1;
                return -1;
            }
        }
        return *p1++;
    }
    inline bool blank(char ch) {
        return ch==' '||ch=='\n'||ch=='\r'||ch=='\t';
    }
    template<class T> inline bool read(T &x) {
        bool sign=0;
        char ch=nc();
        x=0;
        for(; blank(ch); ch=nc());
        if(IOerror)return false;
        if(ch=='-')sign=1,ch=nc();
        for(; ch>='0'&&ch<='9'; ch=nc())x=x*10+ch-'0';
        if(sign)x=-x;
        return true;
    }
    template<class T,class... U>bool read(T& h,U&... t) {
        return read(h)&&read(t...);
    }
#undef OUT_SIZE
#undef BUF_SIZE
};
using namespace std;
using namespace FastIO;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

typedef long long ll;
typedef pair<int,int> pii;
typedef unsigned long long ull;

const int INF = 0x3f3f3f3f;
const int N = 2222;

vector<pii>e[N];
int d[N][N];
int dis[N][N],vis[N][N];

void dij(int s){
	dis[s][s] = 0;
	priority_queue<pii>q;
	q.push(mp(0,s));
	while(!q.empty()){
		int u = q.top().se;
		q.pop();
		if(vis[s][u]) continue;
		vis[s][u] = 1;
		for(auto x:e[u]){
			int v = x.fi;
			int w = x.se;
			if(dis[s][v]>dis[s][u]+w){
				dis[s][v] = dis[s][u]+w;
				q.push(mp(-dis[s][v],v));
			}
		}
	}
}


signed main() {

#ifdef xiaofan
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
#endif

	int n,m;
	cin>>n>>m;
	mem(d,INF);
	for(int i=1;i<=m;i++){
		int u,v,w;
		cin>>u>>v>>w;
		e[u].pb(mp(v,w));
		d[u][v] = min(d[u][v],w);
	}
	mem(dis,INF);
	for(int i=1;i<=n;i++) dij(i);
	for(int i=1;i<=n;i++){
		int ans = d[i][i];
		for(int j=1;j<=n;j++){
			if(i!=j) ans = min(ans,dis[i][j]+dis[j][i]);
		}
		if(ans == INF) ans = -1;
		cout<<ans<<endl;
	}
	




    return 0;
}



