const int N = 10 * 1000 + 13;
const int M = 100 * 1000 + 13;

const int INF = int(1e9);
const int MIN_VAL = -INF;

int n, m;
pair<pair<int, int>, int> g[M];
int d[N];
int p[N];
int used[N];

void fordBellman(int s) {
    for (int i = 0; i < n; i++)
        d[i] = INF;

    d[s] = 0;

    for (int it = 0; it < n; it++) {
        bool wasRelax = false;

        for (int i = 0; i < m; i++) {
            int x = g[i].x.x, y = g[i].x.y, l = g[i].y;

            if (d[x] != INF && d[y] > d[x] + l) {
                d[y] = max(MIN_VAL, d[x] + l);
                p[y] = x;
                wasRelax = true;
            }
        }

        if (!wasRelax)
            break;
    }

    bool negCycleVert = -1;

    for (int i = 0; i < m; i++) {
        int x = g[i].x.x, y = g[i].x.y, l = g[i].y;

        if (d[x] != INF && d[y] > d[x] + l) {
            negCycleVert = x;
            d[y] = MIN_VAL - 1;
        }
    }

    if (negCycleVert != -1) {
        int v = negCycleVert;
        while (!used[v]) {
            used[v] = 1;
            v = p[v];
        }

        vector<int> ans;
        int s = v;
        v = p[v];
        while (v != s) {
            ans.pb(v);
            v = p[v];
        }
        ans.pb(s);

        cout << sz(ans) << endl;
        for (int i = 0; i < n; i++)
            cout << ans[i] + 1 << ' ';
        cout << endl;
    }

    for (int i = 0; i < n; i++) {
        if (d[i] == INF)
            cout << "No path" << endl;
        else if (d[i] == MIN_VAL - 1)
            cout << "Infinity small path" << endl;
        else
            cout << d[i] << endl;
    }
}