package Task10;

import java.util.*;
class Edge{
	int to, weight;
	Edge(int t, int w){
		this.to = t;
		this.weight = w;
	}
}
class Node{
	int heurisitcValue;
	int price;
	Node(){
		heurisitcValue = 0;
		price = 0;
	}
}
class Graph{
	int nodes;
	ArrayList<Edge>[] adj;
	Node[] nodesContainer;
	boolean[] visited;
	@SuppressWarnings("unchecked")
	Graph(int t){
		this.nodes = t;
		this.nodesContainer = new Node[nodes];
		this.visited = new boolean[nodes];
		adj = (ArrayList<Edge>[])new ArrayList[nodes];
		for(int i=0;i<t;i++) {
			this.adj[i] = new ArrayList<Edge>();
			this.nodesContainer[i] = new Node();
		}
	}
	void addEdge(int from, int to, int weight) {
		adj[from].add(new Edge(to,weight));
	}
	int findMin(int s, int t) {
		int r = -1, w = 0;
		int val = Integer.MAX_VALUE;
		for(int i=0;i<adj[s].size();i++) {
			Edge temp = adj[s].get(i);
			if(!visited[temp.to]) {
			    int tempPrice = temp.weight + nodesContainer[temp.to].heurisitcValue;
			    if(val == Integer.MAX_VALUE) {
					val = tempPrice;
					w = temp.weight;
					r = temp.to;
				}
			    if(tempPrice < val) {
					val = tempPrice;
					w = temp.weight;
					r = temp.to;
				}
			}
		}
		//Temp node is either without neighbours or left neighbours left to visit
		if(r==-1) {

			return r;
		}
		visited[r] = true;
		nodesContainer[r].price = val;
		nodesContainer[s].heurisitcValue = Math.min(nodesContainer[s].heurisitcValue +  w,  nodesContainer[r].price);
		return r;
	}
	void findPath(int s, int t) {
		int nextNode = s;
		int prevNode = nextNode;
		for(int i=0;i<nodes;i++) {
			prevNode = nextNode;
			System.out.println(prevNode+" ");
			nextNode = findMin(nextNode,t);
			if(nextNode == t) {
				break;
			}
		}
	}
}
public class Naloga10 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		Graph g = new Graph(5000);
		int totalNodes = 0;
		int m = sc.nextInt();
		for(int i=0;i<m;i++) {
			int f = sc.nextInt(), t = sc.nextInt(), w = sc.nextInt();
			f--;
			t--;
			totalNodes = Math.max(Math.max(f, t), totalNodes);
			g.addEdge(f,t,w);
		}
		g.nodes = totalNodes;
		sc.close();
	}
}