CODEFORCE 459E

cf459e.cpp

#include <cstdio>
#include <cstring>
#include <algorithm>

#define MAX 300007

using namespace std;

struct Edge {
    int u;
    int v;
    int w;
} e[MAX];

bool cmp(Edge& a, Edge& b)
{
    return a.w < b.w;
}

int dp[MAX];
int g[MAX];
int n;
int m;

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; i++) {
        scanf("%d%d%d", &e[i].u, &e[i].v, &e[i].w);
    }
    sort(e, e + m, cmp);
    int t = 0;
    int ans = 0;
    e[m].w = -1;
    for (int i = 0; i < m; i++) {
        dp[i] = g[e[i].u] + 1;
        if (e[i].w != e[i + 1].w) {
            for (int j = t; j <= i; j++) {
                g[e[j].v] = max(g[e[j].v], dp[j]);
            }
            t = i + 1;
        }
        ans = max(ans, dp[i]);
    }
    printf("%d\n", ans);
    return 0;
}