1 /*
2 * File: Timus 1450. Russian pipelines
3 * Author: xiaotian @ hnu
4 * Created on 2010年10月4日, 下午4:06
5 * 题解：DP求最长路
6 */
7 #include<stdio.h>
8 #include<iostream>
9 #include<string.h>
10 using namespace std;
11 #define N 505
12 #define INF 0x7ffffffffLL
13 long long G[N][N], dp[N];
14 bool v[N];
15 int s, t, m, n;
16
17 void dfs(int x) {
18 v[x] = 1;
19 for (int i = 0; i <= n; i++)
20 if (G[i][x] && !v[i]) dfs(i);
21 }
22
23 long long solve(int x) {
24 if (dp[x] != -INF) return dp[x];
25 long long best = -INF, tmp;
26 for (int i = 1; i <= n; i++) {
27 if (G[x][i] && v[i]) {
28 tmp = solve(i) + G[x][i];
29 best = best > tmp ? best : tmp;
30 }
31 }
32 if (best < 0) best = -INF;
33 return dp[x] = best;
34 }
35
36 int main() {
37 while (scanf("%d%d", &n, &m) != EOF) {
38 memset(G, 0, sizeof (G));
39 memset(v, 0, sizeof (v));
40 for (int i = 0; i <= n; i++)
41 dp[i] = -INF;
42 while (m--) {
43 int a, b, c;
44 scanf("%d%d%d", &a, &b, &c);
45 G[b][a] = c > G[b][a] ? c : G[b][a];
46 }
47 scanf("%d%d", &s, &t);
48 dfs(s);
49 dp[s] = 0;
50 long long ret = solve(t);
51 if (ret < 0) printf("No solution");
52 else printf("%lld\n", ret);
53 }
54 return 0;
55 }
56