import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author kessido
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        TaskG solver = new TaskG();
        solver.solve(1, in, out);
        out.close();
    }

    static class TaskG {
        static int[][] g;
        static int n;
        static int[] a;
        static int[][] edges;
        static long[] dp;
        static long[] dpPathToRootWithDetours;
        static int time = 0;
        static int[] appearance;
        static int[] firstAppearance;
        static int[] depth;

        public static void dfs(int i, int parE) {
            firstAppearance[i] = time;
            appearance[time++] = i;
            dp[i] = a[i];
            for (int eIndex : g[i]) {
                if (eIndex == parE) continue;
                int child = i ^ edges[eIndex][0] ^ edges[eIndex][1];
                dfs(child, eIndex);
                appearance[time++] = i;
                dp[i] += Math.max(dp[child] - edges[eIndex][2] * 2, 0);
            }
        }

        public static void dfs2(int i, int parE) {
            if (i == 0) {
                dpPathToRootWithDetours[i] = dp[i];
            } else {
                int par = i ^ edges[parE][0] ^ edges[parE][1];
                depth[i] = depth[par] + 1;
                dpPathToRootWithDetours[i] = dpPathToRootWithDetours[par] - Math.max(0, dp[i] - edges[parE][2] * 2);
                dpPathToRootWithDetours[i] -= edges[parE][2];
                dpPathToRootWithDetours[i] += dp[i];

               ... Which one is the correct time complexity of the code snippet: constant, linear, quadratic, cubic, log(n), nlog(n) or NP-hard?