Problem: You are given a directed acyclic graph (a directed graph that does not contain cycles) of n vertices and m arcs. The i-th arc leads from the vertex x_i to the vertex y_i and has the weight w_i.

Your task is to select an integer a_v for each vertex v, and then write a number b_i on each arcs i such that b_i = a_{x_i} - a_{y_i}. You must select the numbers so that:

  * all b_i are positive; 
  * the value of the expression ∑ _{i = 1}^{m} w_i b_i is the lowest possible. 



It can be shown that for any directed acyclic graph with non-negative w_i, such a way to choose numbers exists.

Input

The first line contains two integers n and m (2 ≤ n ≤ 18; 0 ≤ m ≤ (n(n - 1))/(2)).

Then m lines follow, the i-th of them contains three integers x_i, y_i and w_i (1 ≤ x_i, y_i ≤ n, 1 ≤ w_i ≤ 10^5, x_i ≠ y_i) — the description of the i-th arc.

It is guaranteed that the lines describe m arcs of a directed acyclic graph without multiple arcs between the same pair of vertices.

Output

Print n integers a_1, a_2, ..., a_n (0 ≤ a_v ≤ 10^9), which must be written on the vertices so that all b_i are positive, and the value of the expression ∑ _{i = 1}^{m} w_i b_i is the lowest possible. If there are several answers, print any of them. It can be shown that the answer always exists, and at least one of the optimal answers satisfies the constraints 0 ≤ a_v ≤ 10^9.

Examples

Input


3 2
2 1 4
1 3 2


Output


1 2 0


Input


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


Output


43 42 41 1337 1336


Input


5 5
1 2 1
2 3 1
3 4 1
1 5 1
5 4 10


Output


4 3 2 1 2

Solution (in CPP):

Solution:
//orz Gold_7
//orz SqwrIwy
//orz yzh1505
//orz yzh2019
//orz new
//orz hejinfan
//orz chenkuowen
//#pragma comment(linker,?STACK:1677721600?
#pragma GCC optimize("O2")
#pragma G++ optimize("O2")
#pragma GCC optimize("O3")
#pragma G++ optimize("O3")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
//typedef __int128 ll;
typedef unsigned int uint;
typedef unsigned long long ull;
//typedef double db;
typedef long double ld;
typedef pair<int,int> PII;
typedef pair<ll,int> Pli;
typedef pair<ll,ll> Pll;
typedef vector<int> VI;
typedef vector<PII> VII;
//typedef pair<ll,ll>P;
#define fi first
#define se second
#define MP make_pair
#define pb push_back
#define mem(a,b) memset(a,b,sizeof(a))
#define rep(i,a,b) for(int i=(int)a;i<=(int)b;i++)
#define per(i,a,b) for(int i=(int)a;i>=(int)b;i--)
#define REP(i,n) for(int i=0;i<n;++i)
#define lowbit(x) x&(-x)
#define Rand (rand()*(1<<16)+rand())
#define id(x) ((x)<=B?(x):m-n/(x)+1)
#define fors(i) for(auto i:e[x]) if(i!=p)
#define ls p<<1
#define rs p<<1|1

#define FI(n) FastIO::read(n)
#define FO(n) FastIO::write(n)
#define Flush FastIO::Fflush()

const int N=555555;
const int M=444444;
const int MOD=998244353;
const int intINF=int(1e9);
const ll llINF=ll(2e18);
const uint uintINF=~0U;
const int dx[4]={-1,1,0,0};
const int dy[4]={0,0,-1,1};
const long double pi=acos(-1.0L);
const double eps=1e-8;

int read()
{
   int v=0,f=1;
   char c=getchar();
   while(c<48||57<c) {if(c=='-') f=-1; c=getchar();}
   while(48<=c&&c<=57) v=(v<<3)+v+v+c-48,c=getchar();
   return v*f;
}

ll readll()
{
   ll v=0,f=1;
   char c=getchar();
   while(c<48||57<c) {if(c=='-') f=-1; c=getchar();}
   while(48<=c&&c<=57) v=(v<<3)+v+v+c-48,c=getchar();
   return v*f;
}

void predo()
{
}

int dp[1<<20],w[1<<20];
int g[1<<20][20],pre[1<<20],f[20][20],d[20],num[1<<20],ans[20],
    x[11111],y[11111],flag[1<<20],r[1<<20],n,m;

void init()
{
    n=read(),m=read();
    rep(i,0,n)
     rep(j,0,n) f[i][j]=0;
    rep(i,1,m)
    {
        x[i]=read(),y[i]=read();
        swap(x[i],y[i]);
        int z=read();
        f[x[i]][y[i]]=z;
        d[y[i]]++;
    }
}

void solve()
{
    int mx=(1<<(n+1))-1;

    rep(i,0,n) num[1<<i]=i;

    rep(i,1,n)
    {
        if(!d[i])
        {
           // printf("d[i]=0 i=%d\n",i);
            m++;
            x[m]=0;
            y[m]=i;
            f[0][i]=0;
        }
    }

    rep(s1,0,mx)
    {
        int s2=mx^s1;
        rep(i,0,n)
        {
            if(!(s1>>i&1)) continue;
            rep(j,0,n)
            {
                if(s2>>j&1)
                {
                    w[s1]+=f[i][j];
                    //if(f[i][j]==2e5) w[s1]=intINF;
                }
            }
        }
        //printf("s1=%d w[s1]=%lld\n",s1,w[s1]);
    }

    rep(sta,0,mx)
    {
        flag[sta]=1;
        rep(i,1,m)
        {
            if((sta>>x[i]&1)&&(sta>>y[i]&1)) flag[sta]=0;
        }
    }

    rep(sta,0,mx) dp[sta]=intINF;
    dp[1]=0;

    //printf("predo end\n");

    rep(sta,0,mx)
    {
        r[sta]=0;
        rep(i,1,m)
        {
            if(sta>>x[i]&1) r[sta]|=(1<<y[i]);
        }
        //printf("sta=%d r[sta]=%d\n",sta,r[sta]);
    }

    rep(sta,1,mx)
    {
        pre[sta]=sta;
        int sub=sta;
        while(sub)
        {
            int cost=w[sub];
            //printf("sta=%d sub=%d\n",sta,sub);
            int s=sta^sub;
            if(dp[sub]==intINF||flag[s]==0)
            {
                sub=sta&(sub-1);
                continue;
            }
            if(((s&r[sub])==s)&&((r[s]&sub)==0)&&dp[sub]+cost<dp[sta])
            {
                //printf("sta=%d sub=%d\n",sta,sub);
                dp[sta]=dp[sub]+cost;
                pre[sta]=sub;
            }
            sub=sta&(sub-1);
        }
        //printf("sta=%d dp[sta]=%lld\n",sta,dp[sta]);
    }

    //printf("solve end\n");
    //rep(i,0,n)
     //rep(j,0,mx) printf("i=%d j=%d dp[i][j]=%lld\n",i,j,dp[i][j]);

    int now=mx;
    per(i,n,0)
    {
        int t=pre[now];
        int sta=now-t;
        //printf("i=%d sta=%d\n",i,sta);
        while(sta)
        {
            int tmp=lowbit(sta);
            ans[num[tmp]]=i;
            //printf("v=%d\n",num[tmp]);
            sta-=tmp;
        }
        now=pre[now];
    }
    //printf("ans=%d\n",dp[mx]);
    int mn=1e8;
    rep(i,1,n) mn=min(mn,ans[i]);
    rep(i,1,n) ans[i]=ans[i]-mn+1;
    rep(i,1,n) printf("%d ",ans[i]);
}

int main()
{
    //freopen("1.in","r",stdin);
    //freopen("1.out","w",stdout);
    predo();
    //int cas=read();
    int cas=1;
    while(cas--)
    {
       init();
       solve();
    }
    return 0;
}