#include #include #include #include #include #include #include #include #include static const int MOD = 1000000007; using ll = int64_t; using u32 = uint32_t; using namespace std; template constexpr T INF = ::numeric_limits::max()/32*15+208; template struct edge { int from, to; T cost; edge(int to, T cost) : from(-1), to(to), cost(cost) {} edge(int from, int to, T cost) : from(from), to(to), cost(cost) {} explicit operator int() const {return to;} }; int main() { int n, m; cin >> n >> m; vector>> v(n); for (int i = 0; i < m; ++i) { int a, b, c; cin >> a >> b >> c; v[b].emplace_back(a, c); } vector dp(1<