d['~~'];s[14][14],i,j,u,v,n;main(x){for(n=atoi(gets(&n)),x=1<<n;~scanf("%d%d%d",&i,&j,&u)?s[i][j]=u:x&!!j--<<i?u+=x&1<<j?s[j][i]:0,d[v=x^1<<i]<u?d[v]=u:1:!(u=d[x],j=n,i--)?i=n,x--:1;);i=!printf("%d",*d);}