//Bismillahir Rahmanir Raheem
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair<int,int> pii;
typedef trie<string,null_type,trie_string_access_traits<>,pat_trie_tag,trie_prefix_search_node_update>pref_trie;
#define fi first
#define se second
#define PI 3.14159265
#define mod  11092019
#define ordered_set tree<ll,null_type,less_equal<ll>,rb_tree_tag,tree_order_statistics_node_update>
///order_of_key find_by_order
const ll INFLL = 1e18;
const ll INF =1e9;
const ll EPS =1e-9;
void fast()
{
ios::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
}
ll gcd(ll a,ll b){if(b==0) return a; else return gcd(b,a%b);}
ll lcm(ll a,ll b){ return (a*b)/gcd(a,b);}
ll ncr(ll n,ll r){ ll ans=1;for(ll i=1;i<=r;i++) ans=(ans*(n-i+1))/i;return ans;}
ll cost[2005][2005],vis[2005],n,m;
vector<ll> v[2005];
ll dijsktra(int s)
{
    priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > pq;
    vector<int> dis(n+1,INF);
    pq.push({0,s}); // distance from source node,node number
    dis[s]=0;
    ll ans=INT_MAX;
    while(!pq.empty())
    {
        int num=pq.top().se;
        int num_d=pq.top().fi;
        pq.pop();
        if(num_d!=dis[num]) continue;
        for(int i=0;i<v[num].size();i++)
        {
            if(num_d+cost[num][v[num][i]]<dis[v[num][i]])
            {
                dis[v[num][i]]=num_d+cost[num][v[num][i]];
                pq.push({dis[v[num][i]],v[num][i]});
            }
            if(v[num][i]==s) ans=min(ans,num_d+cost[num][v[num][i]]);
        }
    }
    if(ans==INT_MAX) return -1;
    else return ans;
}
int main()
{

    cin>>n>>m;

    for(int i=0;i<m;i++)
    {
        ll x,y,w;
        cin>>x>>y>>w;
        if(cost[x][y]==0)
        cost[x][y]=w;
        else
        cost[x][y]=min(w,cost[x][y]);
        v[x].push_back(y);
    }
    for(int j=1;j<=n;j++)
    {
        cout<<dijsktra(j)<<endl;
    }
}

#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define ll long long
#define rep(i,n) for (ll i = 0;i<(n);++i)
#define all(v) v.begin(),v.end()

template <typename T>bool chmax(T &a, const T& b) {if (a < b) {a = b;return true;}return false;}
template <typename T>bool chmin(T &a, const T& b) {if (a > b) {a = b;return true;}return false;}
vector<long long> divisor(long long n){vector<long long> res;long long i = 1;while (i*i<=n){if(n%i==0){res.push_back(i);}i++;}if(res.size()==0)return res;for(long long i = res.size()-1-(res.back()*res.back()==n);i>=0;--i){res.push_back(n/res[i]);}return res;}
long long safe_mod(long long x,long long m){x%=m;if(x<0){x+=m;}return x;}
long long modpow(long long x,long long n,long long mod){long long ans=1;while(n>0){if(n&1){ans*=x;ans%=mod;}n>>=1;x*=x;x%=mod;}return ans;}
long long intpow(long long x,long long n){long long ans=1;while(n>0){if(n&1){ans*=x;}n>>=1;x*=x;}return ans;}
vector<pair<long long,long long>> factor_lst(long long n){vector<pair<long long,long long>> factor_lst;long long d=2;while(d*d<=n){if(n%d==0){long long num=0;while(n%d==0){num+=1;n/=d;}factor_lst.push_back({d,num});}d+=1;}if(n!=1){factor_lst.push_back({n,1});}return factor_lst;}

int msb(int x){return x==0 ? -1:32-__builtin_clz(x);}//1-indexed
int lsb(int x){return x==0 ? 32:__builtin_ctz(x)+1;}//1-indexed
int popcnt(int x){return __builtin_popcount(x);}

const ll LINF=4*1e18;
const ll MINF=5*1e15;
const int INF=2*1e9;
template<class T>
class Heap{
    vector<T> v;
    int _size;
    function<bool(T,T)> f;
    int par(int x){return (x-1)>>1;}
    int lch(int x){return (x<<1)+1;}
    int rch(int x){return (x<<1)+2;}
    void downheapify(int i){
        while(1){
        int lchid=lch(i),rchid=rch(i);
        int smallest=i;
        if(lchid<_size&&f(v[lchid],v[smallest]))smallest=lchid;
        if(rchid<_size&&f(v[rchid],v[smallest]))smallest=rchid;
        if(smallest!=i){
            T temp=v[smallest];
            v[smallest]=v[i];
            v[i]=temp;
            i=smallest;
        }
        else break;
        }
    }
    void upheapify(int i){
        T x =v[i];
        while(1){
        if(i==0)break;
        int parid=par(i);
        if(f(x,v[parid])){v[i]=v[parid];}
        else break;
        i=parid;
        }
        v[i]=x;
    }
    public:
    Heap(function<bool(T,T)> _f):v(vector<T>()),_size(0),f(_f){}
    bool empty(){return _size==0;}
    T top(){return v[0];}
    T pop(){
        T res=v[0];
        --_size;
        v[0]=v[_size];
        v.pop_back();
        downheapify(0);
        return res;
    }
    void push(T x){
        v.push_back(x);
        upheapify(_size);
        ++_size;
    }
    vector<T>& get_heap(){return v;}

};

void Main();
int main(){cout<<fixed<<setprecision(15);Main();}

void Main(){
  int N,M;
  cin>>N>>M;
  vector<vector<pair<int,int>>> G(N);
  rep(i,M){
      int A,B,C;
      cin>>A>>B>>C;
      A--;B--;
      G[A].push_back({B,C});

  }
  int ans[N];
  rep(i,N){
      Heap<pair<int,int>> heap([](pair<int,int> p1,pair<int,int> p2){return p1.second<p2.second;});
    ans[i]=INF;
    int dist[N];
    rep(j,N)dist[j]=INF;
    dist[i]=0;
    heap.push({i,0});
    while(!heap.empty()){
        auto p=heap.pop();
        int v=p.first;
        int now=p.second;
        for(auto edge:G[v]){
            int nv=edge.first;
            int len=edge.second;
            int next=now+len;
            if(nv==i){
                chmin(ans[i],next);
            }
            if(next<dist[nv]){
                dist[nv]=next;
                heap.push({nv,next});
            }
        }
    }
  }
  rep(i,N){
      if(ans[i]==INF)cout<<-1<<endl;
      else cout<<ans[i]<<endl;
  }  
}