#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
#define int long long int
#define double long double
#define rep(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))
#define endl '\n'
#define ff first
#define ss second
#define mp make_pair
#define pb push_back
#define pf push_front
#define lb lower_bound
#define ub upper_bound
#define rev(a) a.rbegin(),a.rend()
#define all(a) a.begin(),a.end()
#define setbits(x) (__builtin_popcount(x))
#define pi pair<int,int>
#define fill(s,x,n) vector<s> x(n); rep(i,0,n) cin>>x[i];
#define precise(a,k) cout<<fixed<<setprecision(k)<<a;
#define minpq(type) priority_queue<type,vector<type>,greater<type>>
#define debug(...) cerr<<"{ "<<#__VA_ARGS__<<" = "<<(__VA_ARGS__)<<" }"<<endl;
#define debugp(...) cerr<<"{ "<<#__VA_ARGS__<<" = "<<"("<<(__VA_ARGS__).ff<<","<<(__VA_ARGS__).ss<<")"<<" }"<<endl;
#define debugv(...) cerr<<"{ "; for(int i=0; i<size(__VA_ARGS__); i++) cerr<<#__VA_ARGS__<<"["<<i<<"]"<<" = "<<(__VA_ARGS__)[i]<<" ; "; cerr<<"}"<<endl;
#define debugpv(...) cerr<<"{ "; for(int i=0; i<size(__VA_ARGS__); i++) cerr<<#__VA_ARGS__<<"["<<i<<"]"<<" = "<<"("<<(__VA_ARGS__)[i].ff<<","<<(__VA_ARGS__)[i].ss<<")"<<" ; "; cerr<<"}"<<endl;
#define mod 998244353
#define inf 1000000007
#define inf64 1000000000000000005
#define PI 3.141592653589793

void solve(){
    int n,m;
    cin>>n>>m;
    vector<array<int,2>> adj[n+1];
    vector<array<int,2>> rev[n+1];
    rep(i,0,m){
        int u,v,c;
        cin>>u>>v>>c;
        adj[u].pb({v,c});
        rev[v].pb({u,c});
    }
    rep(i,1,n+1){
        set<pi> s;
        vector<int> d(n+1,inf);
        d[i]=0;
        s.insert({0,i});
        while(!s.empty()){
            int v = s.begin()->ss;
            s.erase(s.begin());
            for(auto pp: adj[v]){
                if(d[pp[0]]>d[v]+pp[1]){
                    s.erase({d[pp[0]],pp[0]});
                    d[pp[0]] = d[v]+pp[1];
                    s.insert({d[pp[0]],pp[0]});
                }
            }
        }
        int ans = inf;
        for(auto pp: rev[i]){
            if(d[pp[0]]!=inf){
                ans = min(ans,d[pp[0]]+pp[1]);
            }
        }
        if(ans==inf) cout<<-1<<endl;
        else cout<<ans<<endl;
    }

}

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    /*
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin); 
    freopen("output.txt", "w", stdout);  
    #endif
    */
    int test;
    //cin>>test;
    test=1;
   // int cse=1;
    while(test--){
       //  cout<<"Case #"<<cse<<": ";//<<endl;
         solve();
         //cout<<endl;
         //cse++;
    }
    cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";
    return 0;
}
#include <bits/stdc++.h>

#define rep(X, N) for (ll X = 0LL; X < (N); X++)
#define ALL(V) (V).begin(), (V).end()
#define endl "\n"
#define pb push_back
#define mp make_pair

using namespace std;
typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;

const double PI = 3.1415926535897932384626;
const ll MODN = 1000000007;
const ll MODN2 = 998244353;

int main(){

    int n;
    cin >> n;
    vector<ll> p(n);
    rep(i, n) cin >> p[i];

    ll diff = 0;
    bool able = true;

    rep(i, n){
        ll tmp = p[i] - (i + 1);
        if(tmp == 0){
            able = false;
            break;
        }
        diff += tmp;
        if(i != n - 1){
            if(diff == 0 || abs(diff) > n - 1){
                able = false;
                break;
            }
        }
    }

    if(!able){
        cout << -1 << endl;
        return 0;
    }

    vector<pair<ll, int>> v(n);

    rep(i, n){
        v[i] = mp(p[i], i + 1);
    }

    sort(ALL(v));
    vector<int> checked(n + 1, 0);
    vector<int> ans;

    ll k = 1;
    while(k <= n - 1){
        //auto itr = lower_bound(ALL(v), mp(k, 0));
        // pの中でkがあるindex
        int kidx = v[k - 1].second;
        for(int i = kidx - 1; i >= k; i--){
            if(checked[i] == 1){
                cout << -1 << endl;
                return 0;
            }
            checked[i] = 1;
            ans.pb(i);
        }
        k = kidx;
    }

    rep(i, n - 1){
        printf("%d\n", ans[i]);
    }
    return 0;
}
