An Important Letter


Submit solution

Points: 12 (partial)
Time limit: 2.0s
Memory limit: 64M

Author:
Problem type

You have an important letter to deliver to Evan. It must be hand-delivered, but because there are so many others after him, you may not be able to reach him directly. There are \(N\) students in the school, who may help you deliver your letter, at a certain cost. Person \(a_i\) will deliver a letter to person \(b_i\) at a cost of \(c_i\). There are \(M\) such options.

You, however, have friends. A friend group is defined as follows: anyone of a friend group is able to deliver a letter directly or indirectly to any other person of the friend group. Formally, the directed edges of a friend group form a cycle. In friend groups, there are no costs of deliver letters.

You would like to find the cheapest cost of delivering your letter to Evan.

Constraints

\(2 \leq N \leq 10^4\)

\(0 \leq M \leq 10^5\)

\(1 \leq A, B, a_i, b_i \leq N\)

\(A \neq B\)

\(a_i \neq b_i\)

\(0 \leq c_i \leq 10^4\)

Input Specification

The first line of input will contain integers \(N, M, A\), and \(B,\) where \(A\) represents you and \(B\) represents Evan.

The next \(M\) lines contain integers \(a_i, b_i, c_i.\)

Output Specification

Print one number, the minimum possible cost of delivering your letter to Evan.

If it is not possible for Evan to receive your message, print No Friends.

Sample Input 1

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

Sample Output 1

8

Explanation

\(1, 2, 3,\) and \(4\) form a friend group, so you can deliver your message to \(4\) at no cost, then \(4\) delivers to \(5,\) then \(5\) to \(6,\) then \(6\) to Evan.

This gives a total cost of \(2 + 1 + 5 = 8\)

Sample Input 2

4 4 1 4
1 2 1
2 3 1
3 2 1
3 4 1

Sample Output 2

2

Comments


  • 6969
    Plasmatic  commented on Jan. 25, 2019, 8:31 p.m.

    eric ur very gay