1450
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <math.h>
#include <limits.h>
 
using namespace std;
 
// Datatypes
typedef vector<int> vi; 
typedef vector<string> vs;
typedef vector<vi> vvi; 
typedef pair<int,int> ii; 
typedef long long ll;
typedef long double ld;
 
// Define
#define sz(a)             int((a).size()) 
#define pb                push_back 
#define all(c)            (c).begin(),(c).end() 
#define present(c,x)      ((c).find(x) != (c).end()) 
#define cpresent(c,x)     (find(all(c),x) != (c).end()) 
#define FOR(_i,_n)        for(int (_i) = 0; (_i) < (_n); (_i)++)
#define mp                make_pair
 
// Constants
const double eps = 1e-8; 
const double PI = 3.1415926535897932384626433832795;
 
#define INPUT_FILE "ladder.in"
#define OUTPUT_FILE "ladder.out"
 
vector< vector< pair<int, int> > > E;
vector< int > vd;
vector< int > r;
list<int> T;
list<int> L;
 
void topsort()
{
    for(int i = 0; i < E.size(); i++)
    {
        if(vd[i] == 0)
        {
            T.push_back(i);
        }
    }
 
    while(T.size() != 0)
    {
        int v = T.front();
        T.pop_front();
 
        L.pb(v);
 
        for(int i = 0; i < E[v].size(); i++)
        {
            vd[E[v][i].first]--;
            if(vd[E[v][i].first] == 0)
                T.pb(E[v][i].first);
        }
    }
}
 
void findpath()
{
    while(L.size() != 0 )
    {
        int v = L.front();
        L.pop_front();
 
        if(r[v] == INT_MIN) continue;
 
        for(int i = 0; i < E[v].size(); i++)
        {
            if(r[E[v][i].first] == INT_MIN)
            {
                r[E[v][i].first] = r[v] + E[v][i].second;
            } else {
                r[E[v][i].first] = max(r[E[v][i].first], r[v] + E[v][i].second);
            }
        }
 
    }
}
 
int main(void)
{
#ifdef ALEX
    freopen("input.in", "r", stdin);
    freopen("output.out", "w", stdout);
#else
    //freopen(INPUT_FILE, "r", stdin);
    //freopen(OUTPUT_FILE, "w", stdout);
#endif
 
    int N,M;
 
    cin >> N >> M;
 
    E.resize(N);
    vd.resize(N);
    r.resize(N);
 
    for(int i = 0; i < N; i++)
        r[i] = INT_MIN;
 
    for(int i = 0; i < M; i++)
    {
        int a,b,d;
        cin >> a >> b >> d;
        E[a-1].pb(mp(b-1,d));
        vd[b-1]++;
    }
 
    int S,F;
 
    cin >> S >> F;
 
    topsort();
    r[S-1] = 0;
 
    findpath();
 
    if(r[F-1] == INT_MIN)
    {
        cout << "No solution";
    }
    else
    {
        cout << r[F-1];
    }
 
    return 0;
}
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-Share Alike 2.5 License.