stablegradients/pie-gem5-bysrc huggingface dataset:
// Original C++ solution (slower):
#include<bits/stdc++.h>

using namespace std;

typedef long long LL;



LL cost[15][15];



int main(){

	ios_base::sync_with_stdio(0);

	

	int h, w;

	LL ans=0;

	cin >> h >> w;

	for(int i=0; i<10; i++){

		for(int j=0; j<10; j++)

			cin >> cost[i][j];

	}

	

	//floyd warshall

	for(int i=0; i<10; i++){

		for(int j=0; j<10; j++){

			for(int k=0; k<10; k++){

				cost[j][k]=min(cost[j][k], cost[j][i]+cost[i][k]);

			}

		}

	}

	

	for(int i=0; i<h; i++){

		for(int j=0; j<w; j++){

			int in;

			cin >> in;

			if(in > -1)

				ans+=cost[in][1];

		}

	}

	

	cout << ans << "\n";

	

	return 0;

}

// Optimized solution to the same problem (faster):
#include <cstdio>

#include <algorithm>



using namespace std;



int C[10][10];

int h, w;



int main() {

    scanf("%d%d", &h, &w);

    for (int i = 0; i < 10; i++)

        for (int j = 0; j < 10; j++) scanf("%d", &C[i][j]);

    for (int k = 0; k < 10; k++)

        for (int i = 0; i < 10; i++)

            for (int j = 0; j < 10; j++) C[i][j] = min(C[i][j], C[i][k] + C[k][j]);

    int ans = 0;

    for (int i = 0, x; i < h; i++)

        for (int j = 0; j < w; j++) scanf("%d", &x), ans += (x==-1)?0:C[x][1];

    printf("%d\n", ans);

    return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
	#include <bits/stdc++.h>



using namespace std;



typedef long long ll;



int r,c,tujuan,x;

ll temp;



int main(){

		cin>>r>>c;

		int dist[10];

		int w[10][10];

        memset(w,-1,sizeof(w));

		for (int i = 0; i <= 9; ++i)

		{

			dist[i] = INT_MAX;

		}

		for (int i = 0; i <= 9; ++i)

		{

			for (int j = 0; j<=9; j++ ){

				cin>>w[i][j];

			}

		}

		priority_queue<pair<ll,ll>> pq;

		dist[1] = 0;

		pq.push(make_pair(-dist[1],1));

		while(!pq.empty()){

			x = pq.top().second;

			pq.pop();

            for (int i = 0; i<=9; i++){

                if (dist[i]>w[i][x] + dist[x]){

                    dist[i] = w[i][x]+dist[x];

                    pq.push(make_pair(-dist[i],i));

                }

            }

		}

		ll res = 0;

		for (int i = 0; i < r; ++i)

		{

			for (int j=0; j<c; j++){

				cin>>tujuan;

				if (tujuan!=-1){

					if (tujuan != 1) res+=dist[tujuan];

				}

			}

		}

		cout<<res<<endl;







	return 0;



}


// Optimized solution to the same problem (faster):
#include <cstdio>

#include <algorithm>



using namespace std;



int C[10][10];

int h, w;



int main() {

    scanf("%d%d", &h, &w);

    for (int i = 0; i < 10; i++)

        for (int j = 0; j < 10; j++) scanf("%d", &C[i][j]);

    for (int k = 0; k < 10; k++)

        for (int i = 0; i < 10; i++)

            for (int j = 0; j < 10; j++) C[i][j] = min(C[i][j], C[i][k] + C[k][j]);

    int ans = 0;

    for (int i = 0, x; i < h; i++)

        for (int j = 0; j < w; j++) scanf("%d", &x), ans += (x==-1)?0:C[x][1];

    printf("%d\n", ans);

    return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

//template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }

template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

 

/* attention

    long longのシフト演算には気をつけよう

    タイポした時のデバッグが死ぬほどきつくなるので変数名は最低3字くらい使った方がいいかも

    sizeは(int)とキャストしよう

    ごちゃごちゃ場合分けを考える前に全探索は考えましたか？

*/



const int inf = 1<<29;



int H, W;

vector<vector<int>> cost(220, vector<int>(220, inf));



void floyd(){

    for(int k=0; k<10; k++){

        for(int i=0; i<10; i++){

            if(cost[i][k] == inf) continue;

            for(int j=0; j<10; j++){

                if(cost[k][j] == inf) continue;



                cost[i][j] = min(cost[i][j], cost[i][k]+cost[k][j]);

            }

        }

    }

}



int main(){

    cin >> H >> W;



    for(int i=0; i<10; i++) for(int j=0; j<10; j++) cin >> cost[i][j];

    

    map<int, int> mp;

    for(int i=0; i<H; i++) for(int j=0; j<W; j++){

        int c; cin >> c;

        mp[c]++;

    }



    floyd();



    ll ans = 0;

    for(int i=0; i<10; i++){

        ans += mp[i]*cost[i][1];

    }



    cout << ans << endl;



}

// Optimized solution to the same problem (faster):
#include <bits/stdc++.h>

using namespace std;

#define rep(i, l, r) for(int i=(l); i<(r); ++i)

typedef long long ll;

typedef unsigned long long ull;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }

template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

 

/* attention

    long longのシフト演算には気をつけよう

    タイポした時のデバッグが死ぬほどきつくなるので変数名は最低3字くらい使った方がいいかも

    sizeは(int)とキャストしよう

    ごちゃごちゃ場合分けを考える前に全探索は考えましたか？

    詰まった時に、別の分野の問題として考え直す（これdpでは？、グラフとしてみればいいのでは？）

    多くの問題はパターンマッチだが、パターンに落とし込むまでが難しく、そのための訓練としてわからない問題をあれこれ色々な角度から考察してみるのではないか

    cin.tie(0);

    ios::sync_with_stdio(false);<- これら、printfとかと併用しない方が良さそう



*/



const ll mod = 1e9+7;



void chmod(ll &M){

    if(M >= mod) M %= mod;

    else if(M < 0){

        M += (abs(M)/mod + 1)*mod;

        M %= mod;

    }

}



int getl(int i, int N) { return i==0? N-1:i-1; };

int getr(int i, int N) { return i==N-1? 0:i+1; };



/* <--------------------------------------------> */



const int inf=1<<29;



vector<vector<int>> d(10, vector<int>(10, inf));



void floyd(){

    rep(k, 0, 10){

        rep(i, 0, 10){

            if(d[i][k]==inf) continue;

            rep(j, 0, 10){

                if(d[j][k]==inf) continue;

                chmin(d[i][j], d[i][k]+d[k][j]);

            }

        }

    }

}



int main(){

    cin.tie(0);

    ios::sync_with_stdio(false);



    int h, w; cin >> h >> w;

    rep(i, 0, 10) rep(j, 0, 10) cin >> d[i][j];

    floyd();



    map<int, int> mp;

    rep(i, 0, h) rep(j, 0, w){

        int a; cin >> a;

        ++mp[a];

    }



    int ans=0;

    rep(i, 0, 10) ans += mp[i]*d[i][1];

    cout << ans << endl;

    

    return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>

#define rep(i,a,b) for(int i=int(a);i<int(b);++i)

#define SIZE 200005

#define INF 1000000005LL

#define MOD 1000000007



using namespace std;

typedef long long int ll;

typedef pair <int,int> P;



int H,W;

int c[11][11];

int V;

struct edge{int to,cost;};

vector<edge> G[SIZE];

int d[SIZE];



void dijkstra(int s){

	priority_queue<P, vector<P>, greater<P>> que;

	fill(d,d+V,INF);

	d[s] = 0;

	que.push(P(0,s));



	while(!que.empty()){

		P p = que.top();que.pop();

		int v = p.second;

		if(d[v] < p.first)continue;

		for(int i=0;i<G[v].size();i++){

			edge e = G[v][i];

			if(d[e.to] > d[v] + e.cost){

				d[e.to] = d[v] + e.cost;

				que.push(P(d[e.to],e.to));

			}

		}

	}

}



int main()

{

	cin >> H >> W;

	V = 10;

	int C;

	rep(i,0,10) rep(j,0,10){

		cin >> C;

		//Gは逆辺のグラフ

		G[j].push_back((edge){i,C});

	}

	dijkstra(1);

	int a,ans=0;

	rep(i,0,H) rep(j,0,W){

		cin >> a;

		ans += d[a];

	}

	cout << ans << endl;

	return 0;

}


// Optimized solution to the same problem (faster):
#include <bits/stdc++.h>

#define rep(i,a,b) for(int i=int(a);i<int(b);++i)

#define SIZE 15

#define INF 1000000005LL

//#define INF 1e18

#define MOD 1000000007



using namespace std;

typedef long long int ll;

typedef pair <int,int> P;



ll d[SIZE][SIZE];

int V;



void warshall_floyd_init(){

  fill(d[0],d[SIZE],INF);

  rep(i,0,SIZE) d[i][i] = 0;

}



//trueなら負の閉路が存在,0_indexed

bool warshall_floyd(){

  rep(k,0,V) rep(i,0,V){

    if(d[i][k]==INF)continue;

    rep(j,0,V){

      if(d[k][j]==INF)continue;

      d[i][j] = min(d[i][j],d[i][k]+d[k][j]);

    }

  }

  rep(i,0,V) if(d[i][i] < 0) return true;

  return false;

}



void add_edge(int a,int b,ll c){

  d[a][b] = c;

}



int h,w;



int main(){

  V=10;

  cin >> h >> w;

  warshall_floyd_init();

  rep(i,0,10){

    rep(j,0,10){

      ll a;

      cin >> a;

      if(i!=j)add_edge(i,j,a);

    }

  }

  warshall_floyd();

  ll ans=0;

  rep(i,0,h) rep(j,0,w){

    int a;

    cin >> a;

    if(a!=1 && a!=-1){

      ans += d[a][1];

    }

  }

  cout << ans << endl;



  return 0;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>

#define REP(i,a,b) for(int i=(a);i<(b);i++)

#define RREP(i,a,b) for(int i=(a);i>=(b);i--)

#define pq priotity_queue

#define P pair<int,int>

#define P2 pair<int,P>

#define P3 pair<int,P2>

typedef long long ll; typedef long double ld;

using namespace std;

const int INF=1e9, MOD=1e9+7, around[]={0,1,1,-1,-1,0,-1,1,0,0};

const ll LINF=1e18;

const ld PI=abs(acos(-1));

int h,w,a[210][210],cost[10][10];



int main(){

	cin >> h >> w;

	REP(i,0,10) REP(j,0,10) cin >> cost[i][j];

	REP(i,0,h) REP(j,0,w) cin >> a[i][j];

	

	REP(k,0,10){

		REP(i,0,10){

			REP(j,0,10){

				cost[i][j]=min(cost[i][j], cost[i][k]+cost[k][j]);

			}

		}

	}

	

	int s=0;

	REP(i,0,h){

		REP(j,0,w){

			if(a[i][j]==-1) continue;

			s+=cost[a[i][j]][1];

		}

	}

	

	cout << s << endl;

	return 0;

}


// Optimized solution to the same problem (faster):
#include <stdio.h>

#define REP(i,a,b) for(int i=(a);i<(b);i++)

#define RREP(i,a,b) for(int i=(a);i>=(b);i++)

int h,w,a,li[15][15],s=0;



int min(int a, int b){

	if(a>b) return b;

	else return a;

}



int main(void){

	scanf("%d %d",&h,&w);

	REP(i,0,10) REP(j,0,10) scanf("%d", &li[i][j]);

	REP(k,0,10) REP(i,0,10) REP(j,0,10) li[i][j]=min(li[i][j], li[i][k]+li[k][j]);

	REP(i,0,h) REP(j,0,w){

		scanf("%d",&a);

		if(a==-1) continue;

		else s+=li[a][1];

	}

	

	printf("%d\n",s);

	return 0;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <iostream>



using namespace std;



const int INF = 100000000;

int c[10][10] = {0};

int d[10] = {0};



void bellman_ford(int s) {

    d[s] = 0;

    for (int i = 0; i < 10; i++) {

        for (int j = 0; j < 10; j++) {

            for (int k = 0; k < 10; k++) {

                if (j == k) continue;

                int cost = c[k][j];

                // cout << c[j][k];

                if (d[j] != INF && d[k] > d[j] + cost) {

                    d[k] = d[j] + cost;

                }

            }

        }

    }

}



int main() {

    int H, W;

    int A[201][201] = {0};

    int ans = 0;



    cin >> H >> W;



    for (int i = 0; i < 10; i++) {

        for (int j = 0; j < 10; j++) {

            cin >> c[i][j];

        }

    }

    for (int i = 0; i < 10; i++) {

        d[i] = INF;

    }



    bellman_ford(1);



    for (int i = 0; i < W; i++) {

        for (int j = 0; j < H; j++) {

            cin >> A[i][j];

            if (A[i][j] != -1) {

                ans += d[A[i][j]];

            }

        }

    }



    cout << ans << endl;



    return 0;

}

// Optimized solution to the same problem (faster):
#include <iostream>



using namespace std;



int main() {

    int H, W, t, ans = 0;

    int c[10][10];



    cin >> H >> W;



    for (int i = 0; i < 10; i++) {

        for (int j = 0; j < 10; j++) {

            cin >> c[i][j];

        }

    }



    for (int k = 0; k < 10; k++) {

        for (int i = 0; i < 10; i++) {

            for (int j = 0; j < 10; j++) {

                c[i][j] = min(c[i][j], c[i][k] + c[k][j]);

            }

        }

    }

    for (int i = 0; i < W; i++) {

        for (int j = 0; j < H; j++) {

            cin >> t;

            if (t != -1) { ans += c[t][1]; }

        }

    }

    cout << ans << endl;



    return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>

using namespace std;



int n,m;

int d[15][15],maze[205][205];



void Floyd()

{

    for(int k=0;k<10;k++)

        for(int i=0;i<10;i++)

            for(int j=0;j<10;j++)

                d[i][j]=min(d[i][j],d[i][k]+d[k][j]);

}



void input()

{

    for(int i=0;i<10;i++){

        for(int j=0;j<10;j++){

            scanf("%d",&d[i][j]);

        }

    }

    for(int i=1;i<=n;i++){

        for(int j=1;j<=m;j++){

            scanf("%d",&maze[i][j]);

        }

    }

}



void solve()

{

    int sum=0;

    Floyd();

    for(int i=1;i<=n;i++){

        for(int j=1;j<=m;j++){

            if(maze[i][j]!=-1){

                sum+=d[maze[i][j]][1];

            }

        }

    }

    printf("%d\n",sum);

}



int main()

{

    scanf("%d%d",&n,&m);

    input();

    solve();

}


// Optimized solution to the same problem (faster):
#include<cstdio>

#include<algorithm>

using namespace std;

int map[10][10];

int h, w;



void floyd(){

    int i, j, k;

    for(k = 0; k<10; k++){

        for(i = 0; i<10; i++){

            for(j = 0; j<10; j++){

                map[i][j] = min(map[i][j], map[i][k] + map[k][j]);

            }

        }

    }

}



int main(){

    int i, j, a;

    while(~scanf("%d%d",&h, &w)){

        for(i = 0; i<10; i++){

            for(j = 0; j<10; j++){

                scanf("%d",&map[i][j]);

            }

        }

        floyd();

        int ans = 0;

        for(i = 0; i<h; i++){

            for(j = 0; j<w; j++){

                scanf("%d",&a);

                if(a!=-1 && a!=1){

                    ans += map[a][1];

                }

            }

        }

        printf("%d\n", ans);

    }

    return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>

 

using namespace std;

 

#define fi first

#define se second

#define mp make_pair

#define pb push_back

 

typedef long long ll;

 

const ll mod = 1e9+7;

const double pi = acos(-1);



int n,t,j,i,k;

int m, c[12][12];

int f[11],bc[11];

int dp[12][12];





int main(){

	memset(f, 0, sizeof f);

	scanf("%d %d", &n, &m);

	for(i=0;i<10;i++){

		for(j=0;j<10;j++){

			scanf("%d", c[i]+j);

			dp[i][j] = c[i][j];

		}

	}

	for(i=0;i<n;i++){

		for(j=0;j<m;j++){

			scanf("%d", &t);

			if(t>=0)

				f[t]++;

		}

	}

	newload:

	for(i=0;i<10;i++){

		for(j=0;j<10;j++){

			for(k=0;k<10;k++){

				if(dp[i][j] > dp[i][k]+dp[k][j]){

					dp[i][j] = dp[i][k]+dp[k][j];

					goto newload;

				}

			}

		}

	}

	int ans =0;

	for(i=0;i<10;i++)

		ans += f[i]*dp[i][1];

	printf("%d\n", ans);

	return 0;

}

// Optimized solution to the same problem (faster):
#include<cstdio>

#include<algorithm>

using namespace std;

int map[10][10];

int h, w;



void floyd(){

    int i, j, k;

    for(k = 0; k<10; k++){

        for(i = 0; i<10; i++){

            for(j = 0; j<10; j++){

                map[i][j] = min(map[i][j], map[i][k] + map[k][j]);

            }

        }

    }

}



int main(){

    int i, j, a;

    while(~scanf("%d%d",&h, &w)){

        for(i = 0; i<10; i++){

            for(j = 0; j<10; j++){

                scanf("%d",&map[i][j]);

            }

        }

        floyd();

        int ans = 0;

        for(i = 0; i<h; i++){

            for(j = 0; j<w; j++){

                scanf("%d",&a);

                if(a!=-1 && a!=1){

                    ans += map[a][1];

                }

            }

        }

        printf("%d\n", ans);

    }

    return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
/**

  *  Worg

  */

#include <iostream>

#include <algorithm>



int cost[10][10];



void Optimize() {

  for (int k = 0; k < 10; k++) {

    for (int i = 0; i < 10; i++) {

      for (int j = 0; j < 10; j++) {

        cost[i][j] = std::min(cost[i][j], cost[i][k] + cost[k][j]);

      }

    }

  }

}



int main() {

  int h, w; std::cin >> h >> w;



  for (int i = 0; i < 10; i++) {

    for (int j = 0; j < 10; j++) {

      std::cin >> cost[i][j];

    }

  }



  Optimize();



  int answer = 0;

  for (int i = 0; i < h; i++) {

    for (int j = 0; j < w; j++) {

      int x; std::cin >> x;



      if (x == 1 || x == -1) continue;



      answer += cost[x][1];

    }

  }



  std::cout << answer << '\n';



  return 0;

}


// Optimized solution to the same problem (faster):
#include<stdio.h>

#include<algorithm>

 

FILE *in, *out;

 

using namespace std;

 

int v[10][10], n;

 

int main ()

{

 

    //fscanf(stdin, "%d", &n);

    n = 10;

    long long toto = 0;

    int l, c;

    scanf("%d %d", &l, &c);

 

    for(int i = 0; i < n; i++) {

            for(int j = 0; j < n; j++) {

                    fscanf(stdin, "%d", &v[i][j]);

                    if (i == j) {

                            v[i][j] = 0x3f3f3f3f;

                    }

            }

    }

 

    for(int k = 0; k < n; k++) {

            for(int i = 0; i < n; i++) {

                    for(int j = 0; j < n; j++) {

                            v[i][j] = min(v[i][j], (v[i][k] + v[k][j]));

                    }

            }

    }

 

    for(int i = 0; i < n; i++) {

            for(int j = 0; j < n; j++) {

                    if (v[i][j] > 0x3f3f3f3f || i == j) {

                            v[i][j] = 0;

                    }

                    //fprintf(stdout, "%d ", v[i][j]);

            }

            //fprintf(stdout, "\n");

    }



    for(int i = 0; i < l; i++) {

        for(int j = 0; j < c; j++) {

            int x;

            scanf("%d", &x);

            if(x != -1) {

                toto += v[x][1];

            }

        }

    }



    printf("%lld", toto);



    return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <iostream>

#include <string>

#include <vector>

#include <algorithm>

#include <cmath>

#include <stdio.h>

#include <queue>

#include <stack>

#include <climits>

#include <map>

#include <set>



using namespace std;



typedef long long ll;

typedef pair<int, int> P;



const ll mod = 1000000007;

const int inf = 1e9;

const long long INF = 1LL << 60;



const int MAX_V = 100010;

struct edge {

    int to,cost;

};

int V;

vector<edge> G[MAX_V];  //重み付き有効グラフの隣接リスト表現

int d[MAX_V];



void dijkstra(int s){

    //greater<P>を指定することでfirstが小さい順に取り出せるようにする

    priority_queue<P, vector<P>,greater<P> > que;

    fill(d,d+V,inf);

    d[s] = 0;

    que.push(P(0,s));



     while(!que.empty()){

         P p = que.top(); que.pop();     // firstは最短距離、secondは頂点の番号

         int v = p.second;

         if(d[v] < p.first) continue;  

         for(int i = 0; i < G[v].size(); i++){

             edge e = G[v][i];

             if(d[e.to] > d[v] + e.cost){

                 d[e.to] = d[v] + e.cost;

                 que.push(P(d[e.to],e.to));

             }

         }

    }

}



int main()

{

    int h,w;

    cin >> h >> w;

    V = 10;

    for(int i = 0; i < 10; i++){

        for(int j = 0; j < 10; j++){

            int c;  cin >> c;

            if(i == j) continue;

            struct edge e;

            e.to = j; e.cost = c;

            G[i].push_back(e);

        }

    }

    int ans = 0;

    for(int i = 0; i < h; i++){

        for(int j = 0; j < w; j++){

            int a; cin >> a;

            if(a == 1 || a == -1) continue;

            dijkstra(a);

            ans += d[1];

        }

    }

    cout << ans << endl;

}


// Optimized solution to the same problem (faster):
#include <iostream>

#include <string>

#include <vector>

#include <algorithm>

#include <cmath>

#include <stdio.h>

#include <queue>

#include <stack>

#include <climits>

#include <map>

#include <set>



using namespace std;



typedef long long ll;

typedef pair<int, int> P;



const ll mod = 1000000007;

const int inf = 1e9;

const long long INF = 1LL << 60;   // INFの値は1152921504606846976



int n;

const int V_MAX = 305;

ll d[V_MAX][V_MAX];



void warshall_floyd(){

    for(int k = 0; k < n; k++){

        for(int i = 0; i < n; i++){

            if(d[i][k] == INF) continue;

            for(int j = 0; j < n; j++){

                if(d[k][j] == INF) continue;

                d[i][j] = min(d[i][j],d[i][k] + d[k][j]);

            }

        }

    }

}



int main()

{

    int h,w;

    n = 10;

    cin >> h >> w;

    int a[h][w];

    for(int i = 0; i < 10; i++){

        for(int j = 0; j < 10; j++){

            cin >> d[i][j];

        }

    }

    for(int i = 0; i < h; i++){

        for(int j = 0; j < w; j++){

            cin >> a[i][j];

        }

    }

    warshall_floyd();

    ll ans = 0;

    for(int i = 0; i < h; i++){

        for(int j = 0; j < w; j++){

            if(a[i][j] == -1) continue;

            else ans += d[a[i][j]][1];

        }

    }

    cout << ans << endl;

}   

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>

using namespace std;

typedef long long i64;

const int MAXN = 100000 + 10;



int N;

i64 sum;

int answer;

vector <pair<int, int>>Adj[MAXN];



inline void addEdge(int u, int v, int w)

{

	Adj[u].emplace_back(v, w);

	Adj[v].emplace_back(u, w);

}



int centroid, val[MAXN], siz[MAXN], mx[MAXN];



void DFS(int cur, int fa)

{

	siz[cur] = 1, mx[cur] = 0;

	for(auto x : Adj[cur])

		if(x.first != fa)

		{

			val[x.first] = x.second;

			DFS(x.first, cur);

			siz[cur] += siz[x.first];

			mx[cur] = max(mx[cur], siz[x.first]);

		}



	mx[cur] = max(mx[cur], N - siz[cur]);

	if(mx[cur] * 2 < N)

		centroid = cur;

	if(siz[cur] * 2 == N)

		answer = val[cur];

	sum += 2LL * min(siz[cur], N - siz[cur]) * val[cur];

}



int main()

{

	int u, v, w;

	answer = 0x7F7F7F7F;

	cin >> N ;

	for(int i = 1; i < N; i++)

		cin >> u >> v >> w, addEdge(u, v, w);



	DFS(1, 0);



	if(answer >= 0x7F7F7F7F)

		for(auto x : Adj[centroid])

			answer = min(answer, x.second);



	cout << sum - answer << endl ;

}


// Optimized solution to the same problem (faster):
#include <cstdio>

#include <algorithm>



using std::min;

using std::max;



const int MAXN=100111;

const int INF=1034567890;



int N;



struct Vert{

	int FE;

	int Size, Val;

} V[MAXN];



struct Edge{

	int y, c, next;

} E[MAXN<<1];



int Ecnt;



void addE(int a, int b, int c){

	++Ecnt;

	E[Ecnt].y=b;E[Ecnt].c=c;E[Ecnt].next=V[a].FE;V[a].FE=Ecnt;

}



void getSize(int at, int f=0){

	V[at].Size=1;

	for(int k=V[at].FE, to;k;k=E[k].next){

		to=E[k].y;

		if(to==f)	continue;

		getSize(to, at);

		V[at].Size+=V[to].Size;

	}

}



void getVal(int at, int f=0){

	V[at].Val=N-V[at].Size;

	for(int k=V[at].FE, to;k;k=E[k].next){

		to=E[k].y;

		if(to==f)	continue;

		getVal(to, at);

		V[at].Val=max(V[at].Val, V[to].Size);

	}

}



int getG(int at, int f=0){

	int ret=at;

	for(int k=V[at].FE, to;k;k=E[k].next){

		to=E[k].y;

		if(to==f)	continue;

		to=getG(to, at);

		if(V[to].Val<V[ret].Val)	ret=to;

	}

	return ret;

}



long long Calc(bool &v){

	long long ret=0LL;

	for(int i=1, s;i<=Ecnt;i+=2){

		s=min(V[E[i].y].Size, V[E[i+1].y].Size);

		ret+=2LL*min(s, N-s)*E[i].c;

		if(s==N-s)	{ret-=(long long)(E[i].c);v=true;}

	}

	return ret;

}



int main(){

	

	scanf("%d", &N);

	

	for(int i=1, a, b, c;i<N;++i){

		scanf("%d%d%d", &a, &b, &c);

		addE(a, b, c);addE(b, a, c);

	}

	

	int at=1;

	getSize(at);getVal(at);at=getG(at);

	

	bool v=false;

	long long Ans=Calc(v);

	if(!v){

		int m=INF;

		for(int k=V[at].FE;k;k=E[k].next)	m=min(m, E[k].c);

		Ans-=(long long)m;

	}

	

	printf("%lld\n", Ans);

	

	return 0;

}

// Fastest known solution for this problem: