https://atcoder.jp/contests/abc352/submissions/53142324

#include<bits/stdc++.h>
using namespace std;
#define N 19
#define M 1<<16
int n,m,fa[N],pre[N],c[N],cnt,ans[N],vis[N*M],vis1[N*M];
vector<int> g[N*M],g1[N*M];
struct node{
	set<int> ans;
	int id,ne,w;
}v[N],temp[N];
void dfs(int x){
	cnt++;
	c[cnt]=x;
	if(v[x].ne){
		dfs(v[x].ne);
	}
	return ;
}
int id(int x,int y){
	return y*(1<<n)+x;
}
int find(int x){
	while(x!=fa[x]){
		int f=find(fa[x]);
		fa[x]=f;
		return f;
	} 
	return x;
}
void merge(int x,int y){
	fa[find(x)]=find(y);
}
void mark(int x){
    if(vis[x]){
    	return ;
    }
	vis[x]=1;
	for(int i=0;i<g1[x].size();i++){
		int ver=g1[x][i];
		g[ver].push_back(x);
		mark(ver);
	}
	return ;
}
void findans(int x){
	if(!vis[x]){
		return ;
	}
	if(vis1[x]){
	    return ;
	}
	vis1[x]=1;
	v[__builtin_popcount(x%(1<<n))].ans.insert(x/(1<<n));
	for(int i=0;i<g[x].size();i++){
		int ver=g[x][i];
		findans(ver);
	}
	return ;
}
signed main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		fa[i]=i;
		v[i].id=i;
		pre[i]=1;
		v[i].w=-1e9;
	}
	for(int i=1;i<=m;i++){
		int u,v1,w;
		cin>>u>>v1>>w;
		if(find(u)==find(v1)){
			continue;
		}
		pre[v1]=0;
		merge(u,v1);
		while(v[u].ne){
			w-=v[u].w;
			u=v[u].ne;
		}
		v[u].ne=v1;
		v[u].w=w;
	}
	for(int i=1;i<=n;i++){
		if(pre[i]){
			dfs(i);
		}
	}
	for(int i=1;i<=n;i++){
		temp[i]=v[c[i]];
	}
	for(int i=1;i<=n;i++){
		v[i]=temp[i];
	}
	for(int i=2;i<=n;i++){
		for(int j=0;j<=(1<<n)-1;j++){
			if(__builtin_popcount(j)!=i){
				continue;
			}
			for(int k=1;k<=n;k++){
				if((j&(1<<k-1))==0){
					continue;
				}
				for(int k1=1;k1<=n;k1++){
					if((j&(1<<k1-1))==0){
						continue;
					}
					if(v[i-1].w!=-1e9){
						if(k1-k!=v[i-1].w){
							continue;
						}
					}
					g1[id(j-(1<<k-1),k1)].push_back(id(j,k));
				}
			}
		}
	}
	for(int i=1;i<=n;i++){
		mark(id((1<<i-1),i));
	}
	for(int i=1;i<=n;i++){
		if(vis[id((1<<n)-1,i)]){
			findans(id((1<<n)-1,i));
		}
	}
	for(int i=1;i<=n;i++){
		if(v[i].ans.size()==1){
			ans[v[i].id]=*v[i].ans.begin();
		}
		else{
			ans[v[i].id]=-1;
		}
	}
	for(int i=1;i<=n;i++){
		cout<<ans[i]<<' ';
	}
	cout<<endl;
	return 0;
}