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

const int N=20;
int n,m,k,a[N],p2,T[N],E[N*N][3],ans=1<<30;
struct node
{
	int c,a,b;
	bool operator<(const node &o)const
	{
		return c>o.c;
	}
}ed[N*N];

int Findx(int x)
{
	if(T[x]==-1)return x;
	return T[x]=Findx(T[x]);
}

void Merge(int a,int b)
{
	int x=Findx(a),y=Findx(b);
	if(x!=y)T[x]=y;
}

void solve()
{
	memset(T,-1,sizeof(T));
	int i,j,now=0;k=0;
	for(i=1;i<=m;i++)
	{
	    if(a[E[i][0]]==2&&a[E[i][1]]==2)
	    	ed[++k]=(node){E[i][2],E[i][0],E[i][1]};
	    else
	        if(a[E[i][0]]!=a[E[i][1]])
	            if(a[E[i][0]]==2||a[E[i][1]]==2)
    	            if((a[E[i][0]]==1&&E[i][1]==1)||(a[E[i][1]]==1&&E[i][0]==1)||(a[E[i][0]]==3&&E[i][1]==n)||(a[E[i][1]]==3&&E[i][0]==n));
	                else now+=E[i][2];
	            else
	                now+=E[i][2];
	    //cerr<<a[E[i][0]]<<" "<<a[E[i][1]]<<" "<<E[i][0]<<" "<<E[i][1]<<"  "<<now<<endl;
	}
	sort(ed+1,ed+1+k);
	for(i=1,j=0;i<=k;i++)
	    if(Findx(ed[i].a)!=Findx(ed[i].b))
	        Merge(ed[i].a,ed[i].b),j++;
	    else
	        now+=ed[i].c;
	if(j==p2-1)
    	ans=min(ans,now);
}

void dfs(int i)
{
	if(i>=n)
	{
		solve();
		return ;
	}
	for(int j=1;j<=3;j++)
	{
	    a[i]=j;
		if(j==2)p2++;
		dfs(i+1);
		if(j==2)p2--;
	}
}

int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	    cin>>E[i][0]>>E[i][1]>>E[i][2];
	a[1]=a[n]=2;p2=2;
	dfs(2);
	cout<<ans;
	return 0;
}