ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

Timus Top Coders: Second Challenge

About     Problems     Submit solution     Judge status     Standings
Contest is over

B. Russian Pipelines

Time limit: 0.5 second
Memory limit: 64 MB

Background

The last year developed into a lot of trouble for independent Russia. Bad harvest, bird flu and - to crown it all - the President, who decided to raise funds to buy new balalaika and tame bear for the child of his first cousin. These factors (especially the last one) shocked the national economics deeply. Counseled with his friends who wear valenki and ushankas, the President resolved to use a traditional method of state budget reinforcement, which implies increasing the gas transportation tax.

Problem

Russian pipeline system consists of N transfer station, some of which are connected by pipelines. For each of M pipelines the numbers of stations A[i] and B[i], which are connected by this pipeline, and its profitability C[i] are known. A profitability of a pipeline is an amount of dollars, which will be daily yielded in taxes by transferring the gas through this pipeline. Each two stations are connected by not more than one pipeline.
The system was built by Soviet engineers, who knew exactly, that the gas was transferred from Ukrainian gas fields to Siberia and not the reverse. That is why the pipelines are unidirectional, i.e. each pipeline allows gas transfer from the station number A[i] to the station number B[i] only. More over, if it is possible to transfer the gas from the station X to the station Y (perhaps, through some intermediate stations), then the reverse transfer from Y to X is impossible. It is known that the gas arrives to the starting station number S and should be dispatched to the buyers on the final station number F.
The President ordered the Government to find a route (i.e. a linear sequence of stations which are connected by pipelines) to transfer the gas from the starting to the final station. A profitability of this route should be maximal. A profitability of a route is a total profitability of its pipelines.
Unfortunately, the President did not consider that some pipelines ceased to exist long ago, and, as a result, the gas transfer between the starting and the final stations may appear to be impossible...

Input

The first line contains the integer numbers N (2 ≤ N ≤ 500) and M (0 ≤ M ≤ 124750). Each of the next M lines contains the integer numbers A[i], B[i] (1 ≤ A[i], B[i] ≤ N) and C[i] (1 ≤ C[i] ≤ 10000) for the corresponding pipeline. The last line contains the integer numbers S and F (1 ≤ S, F ≤ N; S ≠ F).

Output

If the desired route exists, you should output its profitability. Otherwise you should output "No solution".

Sample

inputoutput
6 7
6 5 10
1 4 11
1 2 4
3 1 5
2 4 5
6 3 1
6 1 3
6 4
17

Notes

In the sample, the desired route is a route 6>3>1>4.
Problem Author: Dmitry Kovalioff, Ilya Grebnov, Nikita Rybak
Problem Source: Timus Top Coders: Second Challenge
To submit the solution for this problem go to the Problem set: 1450. Russian Pipelines