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

typedef long long ll;
typedef pair<int, ll> pii;
#define pb push_back

const int MOD = 1e9 + 7, N = 2e5 + 5, K = 60;
vector<pii> g[N];
int sub[N];

ll add(ll x, ll y)
{
    x += y;
    while (x >= MOD)
        x -= MOD;
    while (x < 0)
        x += MOD;
    return x;
}

ll mul(ll x, ll y)
{
    x %= MOD;
    return (x * y) % MOD;
}

int subtree_sum(int cur, int last)
{
    sub[cur] = 1;
    for (pii e : g[cur])
        if (e.first != last)
            sub[cur] += subtree_sum(e.first, cur);
    return sub[cur];
}

void merge(vector<int> &b1, vector<int> &b2)
{
    for (int i = 0; i < K; i++)
        b1[i] += b2[i];
}

vector<int> precompute(vector<vector<int>> &b, int cur, int last)
{
    for (pii e : g[cur])
    {
        if (e.first != last)
        {
            vector<int> tmp = precompute(b, e.first, cur);
            int sz = sub[e.first] - 1;
            for (ll i = 0; i < K; i++)
            {
                if ((e.second >> i) & 1)
                    tmp[i] = sz - tmp[i] + 1;
                b[cur][i] += tmp[i];
            }
        }
    }
    return b[cur];
}

// Binary Exponentiation O(logn)
// n^m mod p
int power(int n, int m, int p)
{
    int res = 1;
    while (m > 0)
    {
        if (m & 1)
            res = (res * 1ll * n) % p;
        n = (n * 1ll * n) % p;
        m /= 2;
    }
    return res;
}

ll dfs(vector<vector<int>> &b, int cur, int last, int n, vector<int> par)
{
    // cout << cur << "\n";
    // for (int i = 0; i < 3; i++)
    //     cout << par[i] << " ";
    // cout << "\n";
    // ll v = 0;
    // for (int i = 0; i < K; i++)
    // {
    //     if (par[i] > 0)
    //     {
    //         v = add(v, mul(1ll << i, par[i]));
    //         v %= MOD;
    //     }
    // }
    // cout << v << "\n";
    ll res = 0;
    for (int i = 0; i < K; i++)
    {
        if (par[i] + b[cur][i] > 0)
        {
            res = add(res, mul(1ll << i, par[i] + b[cur][i]));
            res %= MOD;
        }
    }
    merge(par, b[cur]);
    for (pii e : g[cur])
    {
        if (e.first != last)
        {
            vector<int> tmp = par, ctmp = b[e.first];
            int sz = sub[e.first] - 1;
            for (ll i = 0; i < K; i++)
                if ((e.second >> i) & 1)
                    ctmp[i] = sz - ctmp[i] + 1;
            for (int i = 0; i < K; i++)
                tmp[i] -= ctmp[i];
            sz = n - sub[e.first] - 1;
            for (ll i = 0; i < K; i++)
                if ((e.second >> i) & 1)
                    tmp[i] = sz - tmp[i] + 1;
            res = add(res, dfs(b, e.first, cur, n, tmp));
        }
    }
    return res;
}

ll solve()
{
    int n, u, v;
    ll w;
    cin >> n;
    vector<vector<int>> b(n + 1, vector<int>(K));
    for (int i = 0; i < n - 1; i++)
    {
        cin >> u >> v >> w;
        g[u].pb({v, w});
        g[v].pb({u, w});
    }
    subtree_sum(1, 1);
    precompute(b, 1, 1);
    vector<int> par(K);
    return mul(dfs(b, 1, 1, n, par), 500000004);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cout << solve() << "\n";
    return 0;
}
        
        
/*/ Author : Abhishek Chauhan /*/

#include<bits/stdc++.h>
#include "ext/pb_ds/assoc_container.hpp"
#include "ext/pb_ds/tree_policy.hpp"
using namespace __gnu_pbds;
using namespace std;

// a+b = a^b + 2*(a&b)
// According to Fermat's little theorem, (a^b)%mod = ((a^(b%(mod - 1)))%mod) if mod is a prime number and not the other way round.
// whenever using a comparator return true only if a<b
// make it forward first if it doesnt work do the reverse 
// vector a = ax + ay b = bx + by then dot porduct is |a||b|cos@ //and also for eas you can use (ax*bx)+(ay*by);

#define rep(i,n)             for(int i=0;i<n;i++)
#define int                  long long
#define pb                   push_back
#define mp                   make_pair
#define all(x)               x.begin(),x.end()
#define mod                  1000000007
#define bpop(x)              __builtin_popcountll((x))
#define fastio               ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define endl                 '\n'

template<class T> 
using ordered_set = tree<T, null_type,less<T>, rb_tree_tag,tree_order_statistics_node_update> ;
// find_by_order(k)  returns iterator to kth element starting from 0;
// order_of_key(k) returns count of elements strictly smaller than k;

template<class T>
T power(T x, T y){T res = 1;while (y > 0){ if (y & 1){res = res*x;} y = y>>1;x = x*x;}return res;}
template<class T>
T powermod(T x, T y, T p){T res = 1;x = x % p;while (y > 0){if (y & 1){res = (res*x) % p;}y = y>>1; x = (x*x) % p;}return res;}

int n;
vector<array<int,3>>arr;
int dp[(1<<18)][18];
int solve(int mask,int prev){
    if(mask==((1<<n)-1)){
        int dist = abs(arr[0][0]-arr[prev][0]);
        dist+= abs(arr[0][1]-arr[prev][1]);
        dist+= max((int)0,arr[0][2]-arr[prev][2]);
        return dist;
    }
    int ans =  1e18;
    if(dp[mask][prev]!=-1){
        return dp[mask][prev];
    }
    for(int i=0;i<n;i++){
        if((mask>>i)&1){
            continue;
        }
        int dist = abs(arr[i][0]-arr[prev][0]);
        dist+= abs(arr[i][1]-arr[prev][1]);
        int fuk = dist;
        dist+= max((int)0,arr[i][2]-arr[prev][2]);
        ans = min(ans,dist+fuk+max((int)0,arr[prev][2]-arr[i][2])+solve(mask^(1<<i),prev));
        ans = min(ans,dist+solve(mask^(1<<i),i));
    }   
    return dp[mask][prev]=ans;
}
void snow(){

   cin>>n;
   arr.resize(n);
   rep(i,(1<<(18))){
    rep(j,n){
        dp[i][j] = -1;
    }
   }
   for(int i=0;i<n;i++){
    rep(j,3){
        cin>>arr[i][j];
    }
   }
   int ans = solve((1<<0),0);
   cout<<ans<<endl;
}


int32_t main()
{
    #ifndef ONLINE_JUDGE
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
    fastio;
    int _;
    _=1;
    for(int i=1;i<=_;i++){
        snow();
    }
    return 0;
}




