[백준] P1167

import java.util.ArrayList;
import java.util.Scanner;

public class P1167 { // 인접행렬 풀이 -> 메모리초과, 인접리스트 풀이 -> 시간초과
	private static ArrayList<int[]> graph; // 인접리스트
	private static int n, max;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		graph = new ArrayList<>();

		for (int i = 0; i < n; i++) {
			int node1 = sc.nextInt();
			while (true) {
				int node2 = sc.nextInt();
				if (node2 == -1)
					break;
				int len = sc.nextInt();
				graph.add(new int[] {node1, node2, len});
			}
		}
		
//		for(int[] ele : graph) {
//			System.out.println(ele[0] + "," + ele[1] + "," + ele[2]);
//		}
		
		System.out.println(solution());
		sc.close();
	}

	private static int solution() {
		for (int i = 1; i <= n; i++) {
			dfs(i, new boolean[n + 1], 0);
		}
		return max;
	}

	private static void dfs(int currentNode, boolean[] visit, int distance) {
		visit[currentNode] = true;
		for(int[] components : graph) {
			if(components[0] == currentNode && !visit[components[1]]) {
				dfs(components[1], visit, distance + components[2]);
			}
		}
		max = max < distance ? distance : max;
	}
}