간선 이어가기

정점이 n개이고 간선이 하나도 없는 무향 그래프가 있다. 여기에 가중치가 붙은 간선 m개의 목록이 주어진다. 목록에 있는 간선을 원하는 순서로 하나씩 그래프에 추가하다가, 정점 s와 정점 t가 연결되는 순간 추가를 멈춘다. 연결이란 간선을 따라 한 정점에서 다른 정점으로 갈 수 있다는 뜻이다.

추가 순서를 조정해서, 멈춘 시점에 그래프에 들어 있는 간선의 가중치 합을 최대로 만들려고 한다. 이 합에는 s와 t를 연결한 마지막 간선의 가중치도 들어간다. 이 합의 최댓값을 구하시오.

첫째 줄에 정점의 개수 n과 목록에 있는 간선의 개수 m이 주어진다. ($2 \le n \le 50$, $1 \le m \le 1000$)

다음 m개 줄에 세 정수 a, b, c가 주어진다. 정점 a와 정점 b를 잇는 가중치 c짜리 간선이 목록에 있다는 뜻이다. ($1 \le a, b \le n$, $1 \le c \le 100$, $a \ne b$)

마지막 줄에 두 정점 s와 t가 주어진다. ($1 \le s, t \le n$, $s \ne t$)

같은 두 정점을 잇는 간선이 목록에 여러 개 들어 있을 수 있다. 목록의 간선을 모두 추가하면 그래프는 연결 그래프가 된다.

s와 t가 연결되는 시점까지 추가한 간선의 가중치 합의 최댓값을 첫째 줄에 출력한다.