#include #include #include #define REP(i,a,b) for(int i = (a); i < (b); i++) #define rep(i,a) REP(i,0,(a)) using namespace std; const int MAX = 13; int x, y, N; int X[MAX], Y[MAX]; double W[MAX]; int d[MAX][MAX]; double dp[1 << MAX][MAX]; double cost(int S, int u, int v) { int sum = 0; rep(i,N) if (!(S >> i & 1)) sum += W[i]; return d[u][v]*(100.0+sum)/120.0; } double rec(int S, int v) { if (dp[S][v] >= 0.0) { return dp[S][v]; } if (S == (1 << N)-1) { return 0; } double res = 1 << 30; rep(u,N){ if (u == v) continue; if (!(S >> u & 1)) { double tmp = rec(S|1 << u, u)+cost(S,v,u)+W[u]; if ((S|1 << u) == (1 << N)-1) { double back = (abs(x-X[u])+abs(y-Y[u]))*100.0/120.0; res = min(res, tmp+back); } else { res = min(res, tmp); } } } return dp[S][v] = res; } int main(void) { cin >> x >> y; cin >> N; rep(i,N) cin >> X[i] >> Y[i] >> W[i]; rep(i,N) REP(j,i+1,N) d[i][j] = d[j][i] = abs(X[i]-X[j])+abs(Y[i]-Y[j]); double sumW = accumulate(W,W+N,0); double ans = 1 << 30; rep(s,N){ rep(i,1 << MAX) rep(j,N) dp[i][j] = -1.0; double start = (abs(x-X[s])+abs(y-Y[s]))*(100.0+sumW)/120.0+W[s]; ans = min(ans, rec(1 << s,s)+start); } printf("%.10f",ans); return 0; }