There are n cities and m bidirectional roads in the country. The roads in the country form an undirected weighted graph. The graph is not guaranteed to be connected. Each road has it's own parameter w. You can travel through the roads, but the government made a new law: you can only go through two roads at a time (go from city a to city b and then from city b to city c) and you will have to pay (w_{ab} + w_{bc})^2 money to go through those roads. Find out whether it is possible to travel from city 1 to every other city t and what's the minimum amount of money you need to get from 1 to t.

Input

First line contains two integers n, m (2 ≤ n ≤ 10^5, 1 ≤ m ≤ min((n ⋅ (n - 1))/(2), 2 ⋅ 10^5)).

Next m lines each contain three integers v_i, u_i, w_i (1 ≤ v_i, u_i ≤ n, 1 ≤ w_i ≤ 50, u_i ≠ v_i). It's guaranteed that there are no multiple edges, i.e. for any edge (u_i, v_i) there are no other edges (u_i, v_i) or (v_i, u_i).

Output

For every city t print one integer. If there is no correct path between 1 and t output -1. Otherwise print out the minimum amount of money needed to travel from 1 to t.

Examples

Input


5 6
1 2 3
2 3 4
3 4 5
4 5 6
1 5 1
2 4 2


Output


0 98 49 25 114 

Input


3 2
1 2 1
2 3 2


Output


0 -1 9 

Note

The graph in the first example looks like this.

<image>

In the second example the path from 1 to 3 goes through 2, so the resulting payment is (1 + 2)^2 = 9.

<image>
#include <bits/stdc++.h>
using namespace std;

#define S size()
#define EN end()
#define BE begin()
#define LEN length()

#define endl "\n"
#define cnt count
#define in insert
#define er erase
#define fi first
#define se second
#define ld double
#define int long long

#define gcd __gcd
#define mp make_pair
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define bs binary_search
#define np next_permutation

#define si set<int>
#define sc set<char>
#define mll map<int,int>
#define vi vector<int>
#define vc vector<char>
#define pll pair<int,int>
#define vpi vector<pll>
#define msi multiset<int>
#define msc multiset<char>
#define vvi vector<vector<int>>

#define mod1 1000000007
#define mod2 998244353
#define inf (int)1e9
#define eness(x) __builtin_ctzll(x)
#define nhigh(x) __builtin_popcountll(x)
#define PI 3.1415926535897932384626433832

#define iter(s) for(auto it:s)
#define forl(i,n) for(int i=0;i<n;i++)
#define fore(i,n) for(int i=1;i<=n;i++)
#define forn(i,n) for(int i=n-1;i>=0;i--)
#define forls(i,l,r) for(int i=l;i<r;i++)
#define forns(i,l,r) for(int i=r-1;i>=l;i--)

#define all(v) v.BE,v.EN
#define SORT(ar,n) sort(ar,ar+n)
#define rall(v) v.rbegin(),v.rend()
#define RSORT(ar,n) sort(ar,ar+n,greater<int>())

#define pat int n;cin>>n;
#define wq int q;cin>>q;fore(_,q)
#define nokay cout<<(ok?"Yes\n":"No\n");
#define tak(s) string s;cin>>s;int n=s.LEN;
#define pat1 int n;cin>>n;int ar[n];forl(i,n) cin>>ar[i];
#define pat2 int n,k;cin>>n>>k;int ar[n];forl(i,n) cin>>ar[i];
#define fastio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
//**********************************
vi mf,mi;
int POW(int x,int y);
int MI(int x,int mod);
void pre_f(int x,int mod);
void pre_i(int x,int mod);
int C(int x,int y,int mod);
int bpow(int x,int y,int mod);

int POW(int x,int y){
    return bpow(x,y,inf);
}
int MI(int x,int mod=mod1){
    return bpow(x,mod-2,mod);
}
void pre_f(int x,int mod=mod1){
    mf=vi(x+1,1);
    forls(i,2,x+1){
        mf[i]=mf[i-1]*i;
        mf[i]%=mod;
    }
    return;
}
void pre_i(int x,int mod=mod1){
    mi=vi(x+1);
    forl(i,x+1){
        mi[i]=MI(mf[i],mod);
    }
    return;
}
int C(int x,int y,int mod=mod1){
    if(x<y) return 0;
    int n1=mf[x];
    int n2=mi[y];
    int n3=mi[x-y];
    int res=(n1*n2)%mod;
    res=(res*n3)%mod;
    return res;
}
int bpow(int x,int y,int mod=mod1){
    x%=mod;
    int res=1;
    while(y>0){
        if(y&1){
            res=res*x%mod;
        }
        x=x*x%mod;
        y>>=1;
    }
    return res;
}
//**********************************
const int N=200001;
vector<vector<array<int,2>>> adj(N);
int32_t main(){
    #ifndef ONLINE_JUDGE
        freopen("./input.txt", "r", stdin);
        freopen("./output.txt", "w", stdout);
    #endif
    fastio;
    int n,m;
    cin>>n>>m;
    int dis[n+1][51];
    forl(i,n+1){
        forl(j,51){
            dis[i][j]=inf;
        }
    }

    forl(i,m){
        int u,v,w;
        cin>>u>>v>>w;
        adj[u].pb({v,w});
        adj[v].pb({u,w});
    }
    dis[1][0]=0;
    //i*51+j -> row dom.
    set<array<int,2>> pq;
    pq.in({0,51});
    //int t=100;
    while(!pq.empty()/* && t--*/){
        //auto itt=pq.BE
        set<array<int,2>>::iterator itt=pq.BE;
        array<int,2> x=*itt;
        pq.er(itt);
        int d=x[0],p=x[1]%51,u=x[1]/51;
        iter(adj[u]){
            int v=it[0],w=it[1];
            //cout<<u<<' '<<v<<' '<<p<<"\n";
            if(p==0){
                int dd=(d);
                if(dis[v][w]>dd){
                    set<array<int,2>>::iterator fin=pq.find({dis[v][w],v*51+w});
                    if(fin!=pq.end()){
                        pq.er(fin);
                    }
                    dis[v][w]=dd;
                    pq.in({dd,v*51+w});
                }
            }
            else{
                int dd=(d+(p+w)*(p+w));
                if(dis[v][0]>dd){
                    set<array<int,2>>::iterator fin=pq.find({dis[v][0],v*51});
                    if(fin!=pq.end()){
                        pq.er(fin);
                    }
                    dis[v][0]=dd;
                    pq.in({dd,v*51});
                }
            }
        }
    }
    fore(i,n){
        if(dis[i][0]==inf){
            cout<<-1<<' ';
        }
        else{
            cout<<dis[i][0]<<' ';
        }
    }
    
}