#include <iostream>
#include <algorithm>
#include <vector>
#include <fstream>
#include <queue>

#define INF -0x3f3f3f3f

using namespace std;


class DirectedGraph {
public:
    explicit DirectedGraph(const string &filename) {
        // read the graph from the given file
        ifstream fin(filename);
        int n, m;
        fin >> n >> m;
        this->vertices = n;
        this->edges = m;
        g.resize((unsigned long)(n));
        while(m--) {
            int x, y, cost;
            fin >> x >> y >> cost;
            g[x].push_back(make_pair(y, cost));
        }
    }

    // topological sort using a queue
    // other
    vector <int> tsortQ() {
        queue <int> q;
        vector <int> deg(this->vertices, 0);
        for(int i = 0 ; i < this->vertices; ++ i) {
            for(auto it : g[i])
                ++deg[it.first];
        }
        for(int i = 0 ; i < this->vertices ; ++ i)
            if(!deg[i])
                q.push(i);
        vector <int> ret;
        while(!q.empty()) {
            int node = q.front();
            ret.push_back(node);
            q.pop();
            for(auto it : g[node])
                if(--deg[it.first] == 0)
                    q.push(it.first);
        }
        return ret;
    }

    // topological sort using dfs
    // Tarjan
    vector <int> tsortDfs() {
        vector <int> ret;
        vector <bool> used((unsigned long)(this->vertices), false);
        for(int i = 0 ; i < this->vertices ; ++ i)
            if(!used[i])
                dfs(i, used, ret);
        reverse(ret.begin(), ret.end());
        return ret;
    }
    int longestPath(int x, int y) {
        vector <int> dp(this->vertices, INF);
        dp[x] = 0;
            for(auto el : this->tsortDfs()) {
            if(dp[el] == INF)
                continue;
            for(auto node : g[el])
                dp[node.first] = max(dp[node.first], dp[el] + node.second);
        }
        return dp[y];
    }
    // directed acyclic graph
    bool isDag() {
        return int(tsortQ().size()) == this->vertices;
    }
private:
    // depth first search
    void dfs(int node, vector <bool> &used, vector <int> &ret) {
        used[node] = true;
        for(auto it : g[node])
            if(!used[it.first])
                dfs(it.first, used, ret);
        ret.push_back(node);
    }
    vector <vector <pair<int, int> > > g;
    int vertices, edges;
};

int main() {
    DirectedGraph g("dag.txt");
    if(!g.isDag()) {
        cout << "Not a DAG\n";
        return 0;


    } else {
        cout << "It's a DAG\n";
    }

    for(auto it : g.tsortDfs())
        cout << it + 1 << ' ';
    cout << '\n';
    cout << g.longestPath(0, 1) << '\n';
    cout << g.longestPath(2, 4) << '\n';

    return 0;
}