#include <bits/stdc++.h>
using namespace std;
int src, dst, price = INT_MAX, fsrc, fdst, fprice = INT_MAX;
vector<vector<pair<int,int>>> adj;
vector<bool> visited;
void dfs(int i, int sum) {
visited[i] = true;
for (auto x: adj[i]) {
int c = x.first, p = x.second;
if (!visited[c]) {
dfs(c, sum + p);
}
else if (c == src) {
if (price > sum + p) {
price = sum + p;
dst = i;
}
}
}
}
int main () {
int n;
cin >> n;
int flights;
cin >> flights;
adj = vector<vector<pair<int,int>>>(n);
for (int i = 0; i < flights; ++i) {
int x,y,z;
cin >> x >> y >> z;
adj[x].push_back({y, z});
}
for (int i = 0; i < n; ++i) {
visited = vector<bool>(n, false);
src = i;
dfs(i, 0);
if (price < fprice) {
fsrc = src;
fdst = dst;
fprice = price;
}
}
cout << fprice << endl;
cout << fsrc << endl;
cout << fdst << endl;}
CiNpbmNsdWRlIDxiaXRzL3N0ZGMrKy5oPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKaW50IHNyYywgZHN0LCBwcmljZSA9IElOVF9NQVgsIGZzcmMsIGZkc3QsIGZwcmljZSA9IElOVF9NQVg7CnZlY3Rvcjx2ZWN0b3I8cGFpcjxpbnQsaW50Pj4+IGFkajsKdmVjdG9yPGJvb2w+IHZpc2l0ZWQ7Cgp2b2lkIGRmcyhpbnQgaSwgaW50IHN1bSkgewoJdmlzaXRlZFtpXSA9IHRydWU7Cglmb3IgKGF1dG8geDogYWRqW2ldKSB7CgkJaW50IGMgPSB4LmZpcnN0LCBwID0geC5zZWNvbmQ7CgkJaWYgKCF2aXNpdGVkW2NdKSB7CgkJCWRmcyhjLCBzdW0gKyBwKTsKCQl9CgkJZWxzZSBpZiAoYyA9PSBzcmMpIHsKCQkJaWYgKHByaWNlID4gc3VtICsgcCkgewoJCQkJcHJpY2UgPSBzdW0gKyBwOwoJCQkJZHN0ID0gaTsKCQkJfQoJCX0KCX0KfQppbnQgbWFpbiAoKSB7CglpbnQgbjsKCWNpbiA+PiBuOwoJaW50IGZsaWdodHM7CgljaW4gPj4gZmxpZ2h0czsKCWFkaiA9IHZlY3Rvcjx2ZWN0b3I8cGFpcjxpbnQsaW50Pj4+KG4pOwoKCWZvciAoaW50IGkgPSAwOyBpIDwgZmxpZ2h0czsgKytpKSB7CgkJaW50IHgseSx6OwoJCWNpbiA+PiB4ID4+IHkgPj4gejsKCQlhZGpbeF0ucHVzaF9iYWNrKHt5LCB6fSk7Cgl9CgkKCWZvciAoaW50IGkgPSAwOyBpIDwgbjsgKytpKSB7CgkJdmlzaXRlZCA9IHZlY3Rvcjxib29sPihuLCBmYWxzZSk7CgkJc3JjID0gaTsKCQlkZnMoaSwgMCk7CgkJaWYgKHByaWNlIDwgZnByaWNlKSB7CgkJCWZzcmMgPSBzcmM7CgkJCWZkc3QgPSBkc3Q7CgkJCWZwcmljZSA9IHByaWNlOwoJCX0KCX0KCgljb3V0IDw8IGZwcmljZSA8PCBlbmRsOwoJY291dCA8PCBmc3JjIDw8IGVuZGw7Cgljb3V0IDw8IGZkc3QgPDwgZW5kbDt9Cg==
NAppIGxvdmUgaGFja2VycmFuawpoYWNrZXJyYW5rIGlzIGFuIGF3ZXNvbWUgcGxhY2UgZm9yIHByb2dyYW1tZXJzCmhhY2tlcnJhbmsKaSB0aGluayBoYWNrZXJyYW5rIGlzIGEgZ3JlYXQgcGxhY2UgdG8gaGFuZ291dA==
4
i love hackerrank
hackerrank is an awesome place for programmers
hackerrank
i think hackerrank is a great place to hangout