#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;

#define fi first
#define se second
#define pb push_back
#define mp make_pair



int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	ll n; cin>>n;
	vector<ll> t(n),p(n),s(n); 
	ll ans=1e9;
	ll none=1;
	for(int i=0; i<n; i++){ 
		cin>>t[i]>>p[i]>>s[i];
		if(s[i]-t[i]>0){
			none=0;
			ans = min(ans,p[i]);
		}
	}
	if(none==0) cout<<ans;
	else cout<<-1;
	
}

#include<bits/stdc++.h>
#define INF 7F7F7F7F7F7F7F7F
using namespace std;
typedef long long ll;

int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
#ifdef LOCAL
    freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    clock_t start,end;
    start = clock();
#endif
    void work();
    work();
#ifdef LOCAL
    end = clock();
    cout<<"运行时间"<<(double)(end-start)<<"ms"<<endl;
#endif
    return 0;
}
int n,m;
vector<pair<int, int>> mmap[2005];
// bool operator < (const pair<int, int>& i,const pair<int, int>& j){
//     return i.second<j.second;
// }
void work(){
    cin>>n>>m;
    int a,b,c;
    while(m--){
        cin>>a>>b>>c;
        mmap[a].push_back(make_pair(b,c));
    }
    for(int i=1;i<=n;i++){
        vector<int> d(n+1,(int)1e9);
        d[i]=0;
        priority_queue<pair<int, int>, vector<pair<int, int>>,greater<pair<int, int>> > pq;
        pq.push(make_pair(d[i],i));
        int ans=1e9;
        int flag=0;
        while(!pq.empty()){
            auto topp=pq.top();pq.pop();
            // cout<<topp.second<<endl;
            for(auto j:mmap[topp.second]){
                if(j.first==i) {
                    ans=min(d[topp.second]+j.second,ans);
                }
                if(d[j.first]>d[topp.second]+j.second){
                    d[j.first]=d[topp.second]+j.second;
                    pq.push(make_pair(d[j.first],j.first));
                }
            }
            if(ans<d[topp.second]) break;
        }
        if(ans!=int(1e9))
            cout<<ans<<endl;
        else cout<<-1<<endl;
    }
}   