#include #include #include #include using namespace std; int n; double G[15][15]; double W[15]; double wsum; double x[15],y[15]; double state[15][1<<15]; double dfs(int node,int bit,double w){ if(bit==1) return G[0][node]*(wsum+100)/120.0; if(state[node][bit]) return state[node][bit]; double ret = 1<<30; for(int j=1;j<=n;++j){ if((bit>>j)&1){ ret = min(ret,dfs(j,bit&(~(1<> x[0] >> y[0]; W[0] = 0; cin >> n; for(int i=1;i<=n;++i){ cin >> x[i] >> y[i] >> W[i]; } } void init(){ for(int i=0;i<=n;++i){ for(int j=i+1;j<=n;++j){ G[i][j] = G[j][i] = abs(x[i]-x[j])+abs(y[i]-y[j]); } } for(int i=1;i<=n;++i) wsum+=W[i]; } int main(){ input(); init(); printf("%.10lf\n",dfs(0,(1<<(n+1))-1,0)); return 0; }