#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <limits>
using namespace std;

/*
 * 关键路径算法基于 AOE 网络（Activity on Edge）
 * 图必须是有向无环图（DAG）
 * 每条边 (u -> v) 表示一个活动，权值 w 表示活动耗时
 *
 * 核心步骤：
 *   1. 用拓扑排序顺序计算每个事件的最早发生时间 ve[]
 *   2. 逆拓扑顺序计算每个事件的最晚发生时间 vl[]
 *   3. 找出所有满足 ve[u] + w == vl[v] 的活动（关键活动）
 *   4. 关键活动连线形成关键路径
 */

struct Edge {
    int to;     // 终点事件编号
    int w;      // 活动耗时
};

int main() {
    int n, e;
    cin >> n >> e;

    vector<vector<Edge>> adj(n);    // 邻接表：活动在边上
    vector<int> indeg(n, 0);        // 各事件的入度

    int u, v, w;
    for (int i = 0; i < e; i++) {
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
        indeg[v]++;                 // 事件 v 的前置事件数加 1
    }

    //
    // 第一步：拓扑排序，计算 ve[]
    //
    vector<int> topo;               // 拓扑序
    queue<int> q;                   // 用普通队列即可（要求的是顺序，不是字典序）
    vector<int> ve(n, 0);           // 事件最早发生时间（从起点开始的最长路径）

    // 入度为 0 的事件作为起始点
    for (int i = 0; i < n; i++) {
        if (indeg[i] == 0) q.push(i);
    }

    while (!q.empty()) {
        int x = q.front(); q.pop();
        topo.push_back(x);

        // 用此事件更新其后继事件的最早发生时间
        for (auto &edge : adj[x]) {
            int y = edge.to;
            int cost = edge.w;

            // ve[y] = max(ve[y], ve[x] + cost)
            ve[y] = max(ve[y], ve[x] + cost);

            // 拓扑排序削减入度
            if (--indeg[y] == 0) {
                q.push(y);
            }
        }
    }

    // 如果拓扑序中事件数 != n，则图中存在环
    if ((int)topo.size() != n) {
        cout << "The graph has a cycle. Critical path undefined." << endl;
        return 0;
    }

    //
    // 第二步：逆拓扑序，计算 vl[]
    //
    vector<int> vl(n, numeric_limits<int>::max());

    // 终点事件的最晚时间 = 其最早时间
    // 注意：可能有多个终点，因此我们取所有 ve[] 中的最大值
    int maxEndTime = 0;
    for (int i = 0; i < n; i++) {
        maxEndTime = max(maxEndTime, ve[i]);
    }

    // 所有事件的最晚事件先设为 maxEndTime
    for (int i = 0; i < n; i++) {
        vl[i] = maxEndTime;
    }

    // 按拓扑序的反顺序遍历
    for (int i = n - 1; i >= 0; i--) {
        int x = topo[i];

        // 遍历 x 的所有后继活动
        for (auto &edge : adj[x]) {
            int y = edge.to;
            int cost = edge.w;

            // vl[x] = min(vl[x], vl[y] - cost)
            vl[x] = min(vl[x], vl[y] - cost);
        }
    }

    //
    // 第三步：找关键活动（关键边）
    //
    cout << "Critical Activities:" << endl;

    for (int x = 0; x < n; x++) {
        for (auto &edge : adj[x]) {
            int y = edge.to;
            int cost = edge.w;

            // 判断活动 (x -> y) 是否关键
            if (ve[x] + cost == vl[y]) {
                cout << x << " -> " << y << " (cost = " << cost << ")" << endl;
            }
        }
    }

    cout << "Total project time = " << maxEndTime << endl;

    return 0;
}