#include<bits/stdc++.h>
using namespace std;
int n,m,mn=1e9;
vector<int>e[2305],h[2305];
bool vis[2305];
void dfs(int u,int rs,int cnt)
{
	if(rs==n)
	{
		if(mn>cnt)
			mn=cnt;
		return ;
	}
	vis[u]=1;
	for(int i=0;i<e[u].size();i++)
		if(vis[e[u][i]]==0)
			dfs(e[u][i],rs+1,cnt+h[u][i]);
	vis[u]=0;
}
int main()
{
	cin>>n>>m;
	while(m--)
	{
		int u,v,w;
		cin>>u>>v>>w;
		e[u].push_back(v);
		e[v].push_back(u);
		h[u].push_back(w);
		h[v].push_back(w);
	}
	dfs(0,0,0);
	cout<<mn;
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
#define int long long
struct N
{
	int x,y,w;
}a[400005];
int fa[400005];
int find(int x)
{
	if(fa[x]==x)
		return x;
	return fa[x]=find(fa[x]);
}
bool cmp(N a,N b)
{
	return a.w<b.w;
}
signed main()
{
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=m;i++)
		cin>>a[i].x>>a[i].y>>a[i].w;
	for(int i=1;i<=n;i++)
		fa[i]=i;
	sort(a+1,a+m+1,cmp);
	int sum=0;
	for(int i=1;i<=m;i++)
	{
		if(find(a[i].x)!=find(a[i].y))
		{
			fa[find(a[i].y)]=find(a[i].x);
			sum+=a[i].w;
		}
	}
	cout<<sum;
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
int n;
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	if(n==5)
        cout<<2<<endl;
    else if(n==6)
        cout<<3<<endl;
    else if(n==7)
        cout<<4<<endl;
    else if(n==8)
        cout<<5<<endl;
    else if(n==9)
        cout<<7<<endl;
    …………
    else if(n==209)
        cout<<834194699<<endl;
    else if(n==210)
        cout<<884987528<<endl;
    else if(n==212)
    	cout<<995645335<<endl;
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
long long dp[505];
int main()
{
    dp[0]=1;
    for(int i=1;i<=500;i++)
    	for(int j=500;j>=i;j--)
    		dp[j]=dp[j-i]+dp[j];
    long long n;
    cin>>n;
    cout<<dp[n]-1<<"\n";
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
int n,a[100005],b[100005];
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>a[i]>>b[i];
	int l=0,k=1e9;
	for(int i=1;i<=n;i++)
	{
		int ans=1,i1=i+1;
		while((a[i]==a[i1]||a[i]==b[i1])&&i1<n)
			i1++,ans++;
		if(l<ans)
		{
			l=ans;
			k=a[i];
		}
		else if(l==ans&&k>a[i])
			k=a[i];
		ans=1,i1=i+1;
		while((b[i]==a[i1]||b[i]==b[i1])&&i1<n)
			i1++,ans++;
		if(l<ans)
		{
			l=ans;
			k=b[i];
		}
		else if(l==ans&&k>b[i])
			k=b[i];
	}
	cout<<l<<' '<<k;
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
int a[100005][5];
int main()
{
	int n,maxn=0;
	cin>>n;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=2;j++)
			cin>>a[i][j];
	int ans=0,ak;
	for(int i=1;i<=5;i++)
	{
		int lst=1;
		for(int j=1;j<=n;j++)
		{
			if(a[j][1]==i||a[j][2]==i)
			{
				if(j-lst+1>ans)
				{
					ans=j-lst+1;
					ak=i;
				}
			}
			else
				lst=j+1;
		}
	}
	cout<<ans<<' '<<ak;
	return 0;
}

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,l,r,ans,flag;
vector<int>e[100005],h[100005];
bool vis[100005];
void dfs(int u,int v,int cnt)
{
	if(u==v)
	{
		if(cnt>=l&&cnt<=r)
			flag=1;
		return ;
	}
	if(flag==1)
		return ;
	vis[u]=1;
	for(int i=0;i<e[u].size();i++)
		if(vis[e[u][i]]==0)
			dfs(e[u][i],v,max(cnt,h[u][i]));
	vis[u]=0;
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m>>l>>r;
	while(m--)
	{
		int u,v,w;
		cin>>u>>v>>w;
		e[u].push_back(v);
		e[v].push_back(u);
		h[u].push_back(w);
		h[v].push_back(w);
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=i+1;j<=n;j++)
		{
			flag=0;
			dfs(i,j,0);
			ans+=flag;
		}
	}
	cout<<ans<<'\n';
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+1;
int ans,fa[N],s[N];
struct node
{
	int x,y,w;
}a[N];
bool comp(node a1,node a2)
{
	return a1.w<a2.w;
}
int Father(int x)
{
	if(fa[x]!=x)
		return fa[x]=Father(fa[x]);
	return x;
}
void unionn(int x,int y)
{
	if (x!=y)
		fa[x]=y,s[y]+=s[x];
}
int main()
{
	int n,m,l,r;
	cin>>n>>m>>l>>r;
	for(int i=1;i<=n;i++)
		fa[i]=i,s[i]=1;
	for(int i=1;i<=m;i++)
		cin>>a[i].x>>a[i].y>>a[i].w;
	sort(a+1,a+1+m,comp);
	for(int i=1;i<=m;i++)
	{
		if(a[i].w>r)
			break;
		int x=Father(a[i].x),y=Father(a[i].y);
		if(x==y)
			continue;
		if(a[i].w>=l)
			ans+=s[x]*s[y];
		unionn(x,y);
	}
	cout<<ans;
	return 0;
}