#include<bits/stdc++.h>
using namespace std;
struct jk{
	int u,k;
};
int n,m;
vector<jk>ve[20];
int book[20][1<<20];
int dfs(int now,int sum){
	if(now==n-1){
		return 0;
	}
	if(book[now][sum]!=-1e9){
		return book[now][sum];
	}
	int len=ve[now].size();
	for(int i=0;i<len;i++){
		if(sum&(1<<ve[now][i].u)){
			continue;
		}
		book[now][sum]=max(dfs(ve[now][i].u,sum+(1<<ve[now][i].u))+ve[now][i].k,book[now][sum+(1<<ve[now][i].u)]);
	}
	return book[now][sum];
}
int main(){
	for(int i=0;i<=19;i++){
		for(int j=0;j<=(1<<19);j++){
			book[i][j]=-1e9;
		}
	}
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int s,d,l;
		cin>>s>>d>>l;
		ve[s].push_back(jk{d,l});
	}
	cout<<dfs(0,1);
	return 0;
}

记录