#include <bits/stdc++.h>

using namespace std;
const int N = 1010, M = 5010;
double dist[N];
bool st[N];

int idx, h[N], e[M], w[M], ne[M];
void add(int a, int b, int c) {
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}

// ① dfs找负环的标准模板
bool dfs1(int u) {
    if (st[u]) return 1;
    bool flag = 0;
    st[u] = 1;
    for (int i = h[u]; ~i; i = ne[i]) {
        int v = e[i];
        if (dist[v] > dist[u] + w[i]) {
            dist[v] = dist[u] + w[i];
            flag = dfs1(v);
            if (flag) break;
        }
    }
    // 回溯写法
    st[u] = 0;
    return flag;
}

// ② 标准错误答案
bool dfs2(int u) {
    if (st[u]) return 1;
    bool flag = 0;
    st[u] = 1;
    for (int i = h[u]; ~i; i = ne[i]) {
        int v = e[i];
        if (dist[v] > dist[u] + w[i]) {
            cout << "u=" << u << ",v=" << v << endl;
            dist[v] = dist[u] + w[i];
            flag = dfs2(v);
            if (flag) return 1;
        }
    }
    // 坚决不回溯

    return flag;
}

/*
测试用例：
4 4
1 2 -2
2 3 -6
2 4 1
4 3 -4

结论：图中是没有负环的，应该返回0
*/
int main() {
#ifndef ONLINE_JUDGE
    freopen("361.in", "r", stdin);
#endif
    int n, m;
    scanf("%d %d", &n, &m);
    // 初始化邻接表
    memset(h, -1, sizeof h);
    int a, b, c;
    for (int i = 0; i < m; i++) {
        scanf("%d %d %d", &a, &b, &c);
        add(a, b, c);
    }

    cout << dfs1(1) << endl; // 返回正确解0，表示没有找到负环

    // 如果按不回溯，而是memset的办法，结果就是错误的啦~
    memset(st, 0, sizeof st);
    memset(dist, 0, sizeof dist);
    cout << dfs2(1) << endl; // 返回错误结果1，表示找到负环
    return 0;
}