Problem:


Minimum-Cost Arborescence

Find the sum of the weights of edges of the Minimum-Cost Arborescence with the root r for a given weighted directed graph G = (V, E).

Input

|V| |E| r
s0 t0 w0
s1 t1 w1
:
s|E|-1 t|E|-1 w|E|-1

, where |V| is the number of vertices and |E| is the number of edges in the graph. The graph vertices are named with the numbers 0, 1,..., |V|-1 respectively. r is the root of the Minimum-Cost Arborescence.

si and ti represent source and target verticess of i-th directed edge. wi represents the weight of the i-th directed edge.

Output

Print the sum of the weights the Minimum-Cost Arborescence.

Constraints

1 ≤ |V| ≤ 100

0 ≤ |E| ≤ 1,000

0 ≤ wi ≤ 10,000

G has arborescence(s) with the root r

Sample Input 1

4 6 0
0 1 3
0 2 2
2 0 1
2 3 1
3 0 1
3 1 5

Sample Output 1

6

Sample Input 2

6 10 0
0 2 7
0 1 1
0 3 5
1 4 9
2 1 6
1 3 2
3 4 3
4 2 2
2 5 8
3 5 3

Sample Output 2

11



Sample input:
4 6 0
0 1 3
0 2 2
2 0 1
2 3 1
3 0 1
3 1 5


Sample output:
6

Submission status: Wrong Answer

Solution code:
from sys import stdin
readline = stdin.readline

from heapq import merge, heappop
from collections import defaultdict

v, e, r = map(int, readline().split())
g = defaultdict(list)
for _ in range(e):
    s, t, d = map(int, readline().split())
    if t == r:
        continue
    g[s].append((d, t))
for vi in range(v):
    g[vi].sort()
    
heap = iter(g[r])
rest_tree = set(range(v)) - {r}
cost = 0
while rest_tree:
    d, t = next(heap)
    if t in rest_tree:
        cost += d
        rest_tree -= {t}
        heap = merge(heap, g[t])

print(cost)

Submission status: Wrong Answer

Solution code:
def cycle_cost(cycles, m):
    return sum(m[ci] for cycle in cycles for ci in cycle)

def get_cycle(pre, nxt, root):
    cycles, checked = [], set()

    # root?????£????????????????????????????????§?????????????????????
    checked |= {root}
    que = nxt[root][:]
    while que:
        root_linked = que.pop()
        checked |= {root_linked}
        if nxt[root_linked]:
            que.extend(nxt[root_linked])

    for i in range(len(pre)):
        if i in checked:
            continue

        # ?????°????????§???????????????????????????
        checking = set()
        while i not in checked:
            checked |= {i}
            checking |= {i}
            i = pre[i]
        if i not in checking: # ?????°????????????
            continue

        # ??????????????´???????????????????????°??¨????????¢???   
        checking.clear()
        while i not in checking:
            checking |= {i}
            i = pre[i]            
            
        cycles.append(checking)
    return cycles

from collections import defaultdict
from itertools import product
def chi_liu_edmonds(g, v, r):
    # ?°??????????????????????????±??????????
    m = [float('inf')] * v
    pre = [None] * v
    nxt = defaultdict(list)
    for s, t in product(range(v), repeat=2):
        if g[s][t] < m[t]:
            m[t] = g[s][t]
            pre[t] = s
            nxt[s].append(t)

    cycles = get_cycle(pre, nxt, r)

    # ??¨??¨??£?????????????????´???
    if len(cycles) == 0:
        m[r] = 0
        return sum(m)
    
    not_cycle = set(range(v)).difference(cycles)
    #????´????????????????
    abridger  = {ni:i for i, ni in enumerate(not_cycle)}
    abridger.update({ci:i + len(not_cycle) for i, cycle in enumerate(cycles) for ci in cycle})
    
    v_dash = len(not_cycle) + len(cycles)
    g_dash = [[float('inf')] * v_dash for _ in range(v_dash)]
    for s, t in product(range(v), repeat=2):
        s_dash, t_dash = abridger[s], abridger[t]
        if s_dash != t_dash:
            d = g[s][t] if t in not_cycle else g[s][t] - g[pre[t]][t]
            g_dash[s_dash][t_dash] = d
    return chi_liu_edmonds(g_dash, v_dash, converter[r]) + cycle_cost(cycles, m)

from sys import stdin
readline = stdin.readline

v, e, r = map(int, readline().split())
g = [[float('inf')] * v for _ in range(v)]

for _ in range(e):
    s, t, d = map(int, readline().split())
    if t == r:
        continue
    g[s][t] = d
chi_liu_edmonds(g, v, r)

Submission status: Wrong Answer

Solution code:
from __future__ import division
from collections import defaultdict

class UnionFindSet:
	def __init__(self, nodes):
		self.fa = {}
		for n in nodes:
			self.fa[n] = n

	def find(self, x):
		if self.fa[x] == x:
			return x
		else:
			self.fa[x] = self.find(self.fa[x])
			return self.fa[x]

	def union(self, x, y):
		fx = self.find(x)
		fy = self.find(y)
		if fx == fy:
			return fx
		else:
			self.fa[fx] = fy
			return fy


"""
graph is a hash
graph["nodes"] is a list of all nodes in the graph
graph["edges"] is a list of all edges in the graph in (x, y, w) form
  - x is the first nodes
  - y is the second nodes
  - w is the weight of the edges
graph["relation"] is the graph relation of the graph
"""

def kruscal(graph):
	"kruscal minimum spanning tree algorithm"
	ufset = UnionFindSet(graph["nodes"])

	ret = 0

	for (x, y, w) in sorted(graph["edges"], key = lambda x: x[-1]):
		fx = ufset.find(x)
		fy = ufset.find(y)
		if fx != fy:
			ret += w
			ufset.union(fx, fy)
		else:
			pass
	return ret

def prime(graph, root):
	dis, vis = {}, {}
	for n in graph["nodes"]:
		dis[n] = 10 ** 9
		vis[n] = False

	nodesNum = len(graph["nodes"])

	dis[root], count, ret  = 0, 0, 0
	while count < nodesNum:
		cm, ci = 10 ** 9, -1
		for n in graph["nodes"]:
			if not vis[n] and dis[n] < cm:
				cm = dis[n]
				ci = n
		
		vis[ci] = True
		count += 1
		ret += cm
		for (y, w) in graph["adj"][ci]:
			dis[y] = min(dis[y], w)

	return ret


if __name__ == '__main__':
	V, E, root = map(int, raw_input().strip().split())
	graph = {}
	graph["nodes"] = [i for i in range(V)]
	graph["edges"] = []
	graph["adj"] = defaultdict(list)
	for _ in range(E):
		x, y, w = map(int, raw_input().strip().split())
		graph["edges"].append((x, y, w))
		graph["adj"][x].append((y, w))

	print prime(graph, root)

Submission status: Wrong Answer

Solution code:
import heapq
V,E,root=map(int, input().split())
nodes = [[] for i in range(V)]
cost = [[] for i in range(V)]
for i in range(E):
    s,t,w = map(int, input().split())
    nodes[s].append(t)
    cost[s].append(w)

visited = [False] * V
total = 0
h = [(0,-1,root)]
while h:
    c,s,t = heapq.heappop(h)
    if visited[t]:
        continue
    total += c
    visited[t] = True
    for i in range(len(nodes[t])):
        nv = nodes[t][i]
        if not visited[nv]:
            heapq.heappush(h,(cost[t][i],t,nv))
print(total)

Submission status: Wrong Answer

Solution code:
import heapq


class UnionFind:

    def __init__(self, size):
        # ????????????????????? (???????????£??¨) ??§??????????????°
        # ??£??????????¬????????´??????¨???
        self.table = [-1 for _ in range(size)]

    def find(self, x):
        # ???????????£??¨????±???????
        while self.table[x] >= 0:
            x = self.table[x]
        return x

    def union(self, x, y):
        # ??????
        s1 = self.find(x)
        s2 = self.find(y)
        if s1 != s2:
            if self.table[s1] >= self.table[s2]:
                self.table[s1] += self.table[s2]
                self.table[s2] = s1
            else:
                self.table[s2] += self.table[s1]
                self.table[s1] = s2
        return self.table[s1]


V, E, root = map(int, input().split())
nodes = [[] for i in range(V)]
cost = [[] for i in range(V)]
for i in range(E):
    s, t, w = map(int, input().split())
    nodes[s].append(t)
    cost[s].append(w)
uf = UnionFind(V)
h = []#[(0, -1, root)]
for u in range(V):
    for i in range(len(nodes[u])):
        nv = nodes[u][i]
        # if u < nv:
        heapq.heappush(h, (cost[u][i], u, nv))
total = 0
forest = []
while len(forest) < V - 1 or h:
    c, s, t = heapq.heappop(h)
    if uf.find(s) != uf.find(t):
        uf.union(s,t)
        forest.append((c,s,t))
        total += c
print(total)

Submission status: Wrong Answer

Solution code:
import heapq

nv, ne, r = map(int, input().split())

edges = [set() for _ in range(nv)]
while ne:
    s, t, w = map(int, input().split())
    edges[s].add((w, t))
    ne -= 1

cost = 0
queue = list(edges[r])
heapq.heapify(queue)
visited = [False] * nv
visited[r] = True

while queue:
    edge_cost, t = heapq.heappop(queue)
    if visited[t]:
        continue
    visited[t] = True
    cost += edge_cost
    if all(visited):
        break
    for e in edges[t]:
        if not visited[e[1]]:
            heapq.heappush(queue, e)

print(cost)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from itertools import chain

nv, ne, r = map(int, input().split())

in_edges = defaultdict(set)
out_edges = defaultdict(set)
while ne:
    s, t, w = map(int, input().split())
    in_edges[t].add((w, s))
    out_edges[s].add((w, t))
    ne -= 1


def chu_liu_edmond(vertices):
    global in_edges, out_edges, nv, r

    total_cost = 0
    prev_v = {v: None for v in vertices}
    next_vs = {v: set() for v in vertices}

    for t in vertices:
        if t == r:
            continue
        min_in_w, min_in_s = min(in_edges[t])
        total_cost += min_in_w
        prev_v[t] = min_in_s
        next_vs[min_in_s].add(t)

    visited = {r}
    queue = set(next_vs[r])
    while queue:
        t = queue.pop()
        visited.add(t)
        queue.update(next_vs[t])

    cycles = []
    for i in vertices:
        if i in visited:
            continue

        cycle_vertices = set()
        while i not in visited:
            visited.add(i)
            cycle_vertices.add(i)
            i = prev_v[i]

        # Branched single path from cycle
        if i not in cycle_vertices:
            continue

        # Current cycle_vertices are not necessarily cycle (may contain branch from cycle)
        cycle_vertices, j = {i}, prev_v[i]
        while j != i:
            cycle_vertices.add(j)
            j = prev_v[j]

        cycles.append(cycle_vertices)

    if not cycles:
        return total_cost

    for cycle in cycles:
        vertices.difference_update(cycle)
        vertices.add(nv)

        for v in cycle:
            for w, t in out_edges[v]:
                if t in vertices:
                    out_edges[nv].add((w, t))
                    in_edges[t].remove((w, v))
                    in_edges[t].add((w, nv))
            for w, s in in_edges[v]:
                if s in vertices:
                    new_w = w + min(in_edges[v])[0]
                    in_edges[nv].add((new_w, s))
                    out_edges[s].remove((w, v))
                    out_edges[s].add((new_w, nv))
            del in_edges[v]
            del out_edges[v]

        nv += 1

    return chu_liu_edmond(vertices)


print(chu_liu_edmond(set(range(nv))))

Submission status: Wrong Answer

Solution code:
V, E, r = map(int, raw_input().split())
es = [map(int, raw_input().split()) for i in xrange(E)]

def solve(V, es, r):
    mins = [(10**18, -1)]*V
    for s, t, w in es:
        mins[t] = min(mins[t], (w, s))
    mins[r] = (-1, -1)

    group = [0]*V
    comp = [0]*V
    cnt = 0

    res = sum(map(lambda x: x[0],mins)) + 1

    used = [0]*V
    for v in xrange(V):
        if not used[v]:
            chain = []
            cur = v
            while not used[cur] and cur!=-1:
                chain.append(cur)
                used[cur] = 1
                cur = mins[cur][1]
            if cur!=-1:
                cycle = 0
                for e in chain:
                    group[e] = cnt
                    if e==cur:
                        cycle = 1
                        comp[cnt] = 1
                    if not cycle:
                        cnt += 1
                if cycle:
                    cnt += 1
            else:
                for e in chain:
                    group[e] = cnt
                    cnt += 1

    if cnt == V: return res

    n_es = []
    for s, t, w in es:
        gs = group[s]; gt = group[t]
        if gs == gt:
            continue
        if comp[gt]:
            n_es.append((gs, gt, w - mins[t][0]))
        else:
            n_es.append((gs, gt, w))

    return res + solve(cnt, n_es, group[r])

print solve(V, es, r)

Submission status: Wrong Answer

Solution code:
import heapq

def prim(n, r, path):
  selected = {}
  paths = []
  hq = []
  selected[r] = True

  if r not in path:
    return []

  for s,d,w in path[r]:
    heapq.heappush(hq, (w, [r,d,w]))

  while len(hq) != 0:
    k,root = heapq.heappop(hq)
    if root[1] in selected: continue
    selected[root[1]] = True
    paths.append(root)
    if root[1] in path:
      for s,d,w in path[root[1]]:
        heapq.heappush(hq, (w, [s,d,w]))
  return paths

V,E,r = map(int, raw_input().split())
path = {}
for _ in xrange(E):
  s,t,w = map(int, raw_input().split())
  if s not in path:
    path[s] = []
  path[s].append([s,t,w])
  # if t not in path:
  #   path[t] = []
  # path[t].append([t,s,w])
result = prim(V, r, path)
sumcost = 0
for s,d,v in result:
  sumcost += v
print sumcost

Submission status: Wrong Answer

Solution code:
def edmond(V, paths, root):
  mins = [(10**18, -1)]*V
  for s,t,w in paths:
    mins[t] = min(mins[t], (w,s))
  mins[r] = (-1, -1)
  group = [0]*V
  comp = [0]*V
  cnt = 0

  used = [0]*V
  for v in xrange(V):
    if not used[v]:
      chain = []
      cur = v
      while not used[cur] and cur != -1:
        chain.append(cur)
        used[cur] = 1
        cur = mins[cur][1]
      if cur != -1:
        cycle = 0
        for e in chain:
          group[e] = cnt
          if e == cur:
            cycle = 1
            comp[cnt] = 1
          if not cycle:
            cnt += 1
        if cycle:
          cnt += 1
      else:
        for e in chain:
          group[e] = cnt
          cnt += 1
  if cnt == V:
    return sum(map(lambda x:x[0], mins)) + 1
  res = sum(mins[v][0] for v in xrange(V) if v != r and comp[group[v]])

  n_es = []
  for s,t,w in paths:
    gs = group[s]
    gt = group[t]
    if gs == gt:
      continue
    if comp[gt]:
      n_es.append((gs, gt, w-mins[t][0]))
    else:
      n_es.append((gs, gt, w))

  return res + edmond(cnt, n_es, group[r])

V,E,r = map(int, raw_input().split())
paths = [map(int, raw_input().split()) for _ in xrange(E)]
print edmond(V, paths, r)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""
input:
6 9
0 1 1
0 2 3
1 2 1
1 3 7
2 4 1
1 4 3
3 4 1
3 5 1
4 5 6

output:
5
"""

import sys
import heapq as hp

WHITE, GRAY, BLACK = 0, 1, 2


def generate_adj_table(v_table):
    for each in v_table:
        v_from, v_to, edge_weight = map(int, each)
        init_adj_table[v_from][v_to] = edge_weight
        # init_adj_table[v_to][v_from] = edge_weight

    return init_adj_table


def prim_span_tree():
    distance[init_v] = root
    distance_heap = []
    hp.heappush(distance_heap, (0, init_v))

    while distance_heap:
        current_vertex = hp.heappop(distance_heap)[1]

        color[current_vertex] = BLACK

        for adj, cost in adj_table[current_vertex].items():
            if color[adj] is not BLACK:
                if cost < distance[adj]:
                    distance[adj] = cost
                    parent[adj] = current_vertex
                    color[adj] = GRAY
                    hp.heappush(distance_heap, (cost, adj))

    return distance


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    vertices, edges, root = map(int, _input[0].split())
    v_info = map(lambda x: x.split(), _input[1:])

    parent = [-1] * vertices
    distance = [float('inf')] * vertices
    color = [WHITE] * vertices
    init_v = 0

    init_adj_table = tuple(dict() for _ in range(vertices))
    adj_table = generate_adj_table(v_info)
    print(sum(prim_span_tree()))

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""
input:

6 10 0
0 2 7
0 1 1
0 3 5
1 4 9
2 1 6
1 3 2
3 4 3
4 2 2
2 5 8
3 5 3

output:
11
"""

import sys
import heapq as hp

WHITE, GRAY, BLACK = 0, 1, 2


def generate_adj_table(v_table):
    for each in v_table:
        v_from, v_to, edge_weight = map(int, each)
        init_adj_table[v_from][v_to] = edge_weight
        # init_adj_table[v_to][v_from] = edge_weight

    return init_adj_table


def prim_span_tree():
    distance[init_v] = root
    distance_heap = []
    hp.heappush(distance_heap, (0, init_v))

    while distance_heap:
        current_vertex = hp.heappop(distance_heap)[1]

        color[current_vertex] = BLACK

        for adj, cost in adj_table[current_vertex].items():
            if color[adj] is not BLACK:
                if cost < distance[adj]:
                    distance[adj] = cost
                    parent[adj] = current_vertex
                    color[adj] = GRAY
                    hp.heappush(distance_heap, (cost, adj))

    return distance


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    vertices, edges, root = map(int, _input[0].split())
    v_info = map(lambda x: x.split(), _input[1:])

    parent = [-1] * vertices
    distance = [float('inf')] * vertices
    color = [WHITE] * vertices
    init_v = 0

    init_adj_table = tuple(dict() for _ in range(vertices))
    adj_table = generate_adj_table(v_info)
    print(sum(prim_span_tree()))

Submission status: Wrong Answer

Solution code:
import heapq as pq
n,E,r = map(int, input().split())
M = [[] for i in range(n)]

for i in range(E):
 s,t,w = map(int, input().split())
 M[s].append([t,w])

def prim(r):
 color = [0] * n
 d = [float("inf")] * n
 d[r] = 0
 H = []
 pq.heappush(H, [0, r])
 while H:
  u2,u1 = pq.heappop(H)
  color[u1] = 1
  if d[u1] < u2: continue
  for v1, v2 in M[u1]:
   if color[v1] == 1: continue
   if d[v1] > v2:
    d[v1] = v2
    pq.heappush(H, [d[v1], v1])
 return sum(d)
 
print(prim(r))

Submission status: Wrong Answer

Solution code:
import heapq as pq
n,E,r = map(int, input().split())
M = [[] for i in range(n)]

for i in range(E):
 s,t,w = map(int, input().split())
 M[s].append([t,w])

def prim(r):
 d = [float("inf")] * n
 d[r] = 0
 H = []
 pq.heappush(H, [0, r])
 while H:
  u2,u1 = pq.heappop(H)
  if d[u1] < u2: continue
  for v1, v2 in M[u1]:
   if d[v1] > v2:
    d[v1] = v2
    pq.heappush(H, [d[v1], v1])
 return sum(d)
 
print(prim(r))

Submission status: Wrong Answer

Solution code:

class Node:
    def __init__(self):
        pass

class Edge:
    def __init__(self,edge,cost=1):
        self.node_from=edge[0]
        self.node_to=edge[1]
        self.cost=cost

    def add_node(self,node):
        self.nodes.append(node)

class myGraph:

    def __init__(self):
        self.adj={}
        self.nodes={}

    def add_edge(self,edge,cost):
        if len(edge)==1:
            edge=list(edge)

        u,v=edge[0],edge[1]

        if u not in self.nodes:
            self.adj[u] = {}
            self.nodes[u] = {}

        if v not in self.nodes:
            self.adj[v] = {}
            self.nodes[v] = {}

        # add the edge
        self.adj[u][v] = cost
        self.adj[v][u] = cost

    def add_directed_edge(self,edge,cost):
        if len(edge)==1:
            edge=list(edge)


        u,v=edge[0],edge[1]

        if u not in self.nodes:
            self.adj[u] = {}
            self.nodes[u] = {}

        if v not in self.nodes:
            self.adj[v] = {}
            self.nodes[v] = {}

        self.adj[u][v] = cost

    def get_edges_from(self,node):
        return [(self.adj[node][nn],node,nn) for nn in self.adj[node]]


    def makeEdgeobj(self):
        edges=[]
        for sn in self.nodes:
            for e in self.get_edges_from(sn):
                edges.append(Edge([e[1],e[2]],e[0]))

        return edges

    def _add(self,edges,add_edges):
        for e in add_edges:
            hq.heappush(edges,e)
        return edges

    def bermn_ford(self,start,init=0):

        nodes=self.nodes
        dists={}
        for n in nodes:
            dists[n]=float("inf")

        dists[start]=init
        edges=self.makeEdgeobj()

        for i in range(len(nodes)):
            update=False
            for k in range(len(edges)):
                e=edges[k]
                if  dists[e.node_from]!=float("inf") and dists[e.node_to]>dists[e.node_from]+e.cost:
                    dists[e.node_to]=dists[e.node_from]+e.cost
                    update=True

            if i==len(nodes)-1:
                return False

            if not update:
                break

        return dists


    def dijkstra(self,start, goal=None):
        import heapq
        '''
            get minimum cost
        '''

        N = len(self.adj)          # ??°????????????????????°
        #dist = [float('inf') for i in range(N)] # ?§????????????????????????§??????????????¢???????´???????
        dist = {k:float('inf') for k in self.nodes}
        #prev = [float('inf') for i in range(N)]

        dist[start] = 0
        visited = []

        koho=[]
        heapq.heappush(koho,(0,start))

        vtx=list(self.nodes)
        vtx.remove(start)

        while len(koho)!=0:
            d,mini=heapq.heappop(koho)
            if dist[mini]<d:
                continue


            for k in list(self.adj[mini]):
                cost=self.adj[mini][k]
                if cost != float('inf') and dist[k]>dist[mini]+cost:# and not(k in visited):
                    dist[k]=dist[mini]+cost
                    heapq.heappush(koho,(dist[k],k))
                    #prev[k]=mini

        return dist

    def prim(self):
        import heapq

        nodes=list(self.nodes.keys())
        N=len(nodes)

        X=[nodes[0]]
        unused=[]
        for u in self.adj[X[0]]:
            heapq.heappush(unused,(u,self.adj[X[0]][u]))

        total_cost=0
        while True:
            v,cost=heapq.heappop(unused)

            X.append(v)
            total_cost+=cost
            if len(X)==N:
                break

            for u in self.adj[v]:
                heapq.heappush(unused,(u,self.adj[v][u]))



        return total_cost




    def show(self):

        import networkx as nx
        import matplotlib.pyplot as plt
        G=nx.Graph()

        for e in self.edges:

            G.add_edge(e.node_from,e.node_to,weight=e.cost)
            #print(e.node_from,e.node_to,e.cost)

        pos=nx.spring_layout(G)
        #nx.draw_networkx_edges(G,pos=pos,edgelist=G.edges())
        edge_weight=dict([((u,v,),int(d['weight'])) for u,v,d in G.edges(data=True)])

        nx.draw_networkx_edge_labels(G,pos,edge_labels=edge_weight)
        #nx.draw_networkx_labels(G, pos)
        nx.draw_networkx_nodes(G,pos)
        nx.draw_networkx_edges(G,pos)
        nx.draw_networkx_labels(G,pos)
        #plt.axis('off')
        #nx.draw(G,with_labels=True)
        plt.show()



def spaceinput():
    s=input()
    if len(s)==0:
        return False

    return list(map(int,s.split(" ")))

if __name__=="__main__":
    a=spaceinput()
    g=myGraph()


    for i in range(999):
        try:
            ss=spaceinput()
            if not ss:
                break
        except:
            break

        g.add_edge((ss[0],ss[1]),ss[2])

    print(g.prim())

    '''
    d=g.dijkstra(1)
    '''



    '''
    mint=10*9
    for k in range(1,n+1):
        dd=g.dijkstra(k)
        v=max(dd.values())
        if mint>v:
            mint=v


    print(mint)
    '''

Submission status: Wrong Answer

Solution code:

class Node:
    def __init__(self):
        pass

class Edge:
    def __init__(self,edge,cost=1):
        self.node_from=edge[0]
        self.node_to=edge[1]
        self.cost=cost

    def add_node(self,node):
        self.nodes.append(node)

class myGraph:

    def __init__(self):
        self.adj={}
        self.nodes={}

    def add_edge(self,edge,cost):
        if len(edge)==1:
            edge=list(edge)

        u,v=edge[0],edge[1]

        if u not in self.nodes:
            self.adj[u] = {}
            self.nodes[u] = {}

        if v not in self.nodes:
            self.adj[v] = {}
            self.nodes[v] = {}

        # add the edge
        self.adj[u][v] = cost
        self.adj[v][u] = cost

    def add_directed_edge(self,edge,cost):
        if len(edge)==1:
            edge=list(edge)


        u,v=edge[0],edge[1]

        if u not in self.nodes:
            self.adj[u] = {}
            self.nodes[u] = {}

        if v not in self.nodes:
            self.adj[v] = {}
            self.nodes[v] = {}

        self.adj[u][v] = cost

    def get_edges_from(self,node):
        return [(self.adj[node][nn],node,nn) for nn in self.adj[node]]


    def makeEdgeobj(self):
        edges=[]
        for sn in self.nodes:
            for e in self.get_edges_from(sn):
                edges.append(Edge([e[1],e[2]],e[0]))

        return edges

    def _add(self,edges,add_edges):
        for e in add_edges:
            hq.heappush(edges,e)
        return edges

    def bermn_ford(self,start,init=0):

        nodes=self.nodes
        dists={}
        for n in nodes:
            dists[n]=float("inf")

        dists[start]=init
        edges=self.makeEdgeobj()

        for i in range(len(nodes)):
            update=False
            for k in range(len(edges)):
                e=edges[k]
                if  dists[e.node_from]!=float("inf") and dists[e.node_to]>dists[e.node_from]+e.cost:
                    dists[e.node_to]=dists[e.node_from]+e.cost
                    update=True

            if i==len(nodes)-1:
                return False

            if not update:
                break

        return dists


    def dijkstra(self,start, goal=None):
        import heapq
        '''
            get minimum cost
        '''

        N = len(self.adj)          # ??°????????????????????°
        #dist = [float('inf') for i in range(N)] # ?§????????????????????????§??????????????¢???????´???????
        dist = {k:float('inf') for k in self.nodes}
        #prev = [float('inf') for i in range(N)]

        dist[start] = 0
        visited = []

        koho=[]
        heapq.heappush(koho,(0,start))

        vtx=list(self.nodes)
        vtx.remove(start)

        while len(koho)!=0:
            d,mini=heapq.heappop(koho)
            if dist[mini]<d:
                continue


            for k in list(self.adj[mini]):
                cost=self.adj[mini][k]
                if cost != float('inf') and dist[k]>dist[mini]+cost:# and not(k in visited):
                    dist[k]=dist[mini]+cost
                    heapq.heappush(koho,(dist[k],k))
                    #prev[k]=mini

        return dist

    def prim(self):
        import heapq

        nodes=list(self.nodes.keys())
        N=len(nodes)

        X=[nodes[0]]
        unused=[]
        for u in self.adj[X[0]]:
            heapq.heappush(unused,(self.adj[X[0]][u],u))

        total_cost=0
        while True:
            #print(unused)
            cost,v=heapq.heappop(unused)

            X.append(v)
            total_cost+=cost
            if len(X)==N:
                break

            for u in self.adj[v]:
                if u in X:
                    continue
                heapq.heappush(unused,(self.adj[v][u],u))

        return total_cost




    def show(self):

        import networkx as nx
        import matplotlib.pyplot as plt
        G=nx.Graph()

        for u in self.adj:
            for v in self.adj[u]:

                #G.add_edge(e.node_from,e.node_to,weight=e.cost)
                G.add_edge(u,v,weight=self.adj[u][v])
                #print(e.node_from,e.node_to,e.cost)

        pos=nx.spring_layout(G)
        #nx.draw_networkx_edges(G,pos=pos,edgelist=G.edges())
        edge_weight=dict([((u,v,),int(d['weight'])) for u,v,d in G.edges(data=True)])

        nx.draw_networkx_edge_labels(G,pos,edge_labels=edge_weight)
        #nx.draw_networkx_labels(G, pos)
        nx.draw_networkx_nodes(G,pos)
        nx.draw_networkx_edges(G,pos)
        nx.draw_networkx_labels(G,pos)
        #plt.axis('off')
        #nx.draw(G,with_labels=True)
        plt.show()



def spaceinput():
    s=input()
    if len(s)==0:
        return False

    return list(map(int,s.split(" ")))

if __name__=="__main__":
    a=spaceinput()
    g=myGraph()


    for i in range(999):
        try:
            ss=spaceinput()
            if not ss:
                break
        except:
            break

        #g.add_edge((ss[0],ss[1]),ss[2])
        g.add_directed_edge((ss[0],ss[1]),ss[2])

    #print(g.show())
    print(g.prim())

    '''
    d=g.dijkstra(1)
    '''



    '''
    mint=10*9
    for k in range(1,n+1):
        dd=g.dijkstra(k)
        v=max(dd.values())
        if mint>v:
            mint=v


    print(mint)
    '''