#include #define rep(i, n) for(long long i = 0; i < n; i++) #define ALL(v) (v).begin(), (v).end() using namespace std; using lint = long long; template struct WeightedUnionFind { private: int n; vector par; vector diff_weight; public: WeightedUnionFind() {} WeightedUnionFind(int n_) : n(n_), par(n, -1), diff_weight(n, T(0)) {} int leader(int x) { assert(0 <= x && x < n); if (par[x] < 0) { return x; } else { int r = leader(par[x]); diff_weight[x] += diff_weight[par[x]]; return par[x] = r; } } T weight(int x) { assert(0 <= x && x < n); leader(x); return diff_weight[x]; } T diff(int x, int y) { assert(0 <= x && x < n); assert(0 <= y && y < n); return weight(y) - weight(x); } int merge(int x, int y, T w) { assert(0 <= x && x < n); assert(0 <= y && y < n); w += weight(x); w -= weight(y); x = leader(x); y = leader(y); if (x == y) { return x; } if (-par[x] < -par[y]) { swap(x, y); w *= T(-1); } par[x] += par[y]; par[y] = x; diff_weight[y] = w; return x; } bool same(int x, int y) { assert(0 <= x && x < n); assert(0 <= y && y < n); return leader(x) == leader(y); } int size(int x) { assert(0 <= x && x < n); return -par[leader(x)]; } vector> groups() { vector> member(n); for (int i = 0; i < n; i++) { member[leader(i)].emplace_back(i); } vector> res; for (int i = 0; i < n; i++) { if (member[i].size() > 0) { res.emplace_back(member[i]); } } return res; } }; template struct Edge { int from, to; T cost; int idx; Edge() {} Edge(int to_) : to(to_) {} Edge(int to_, T cost_) : to(to_), cost(cost_) {} Edge(int from_, int to_, int idx_) : from(from_), to(to_), idx(idx_) {} Edge(int from_, int to_, T cost_, int idx_) : from(from_), to(to_), cost(cost_), idx(idx_) {} }; template using Graph = vector>>; using graph = Graph; using edge = Edge; #define add emplace_back struct Dijkstra { private: graph g; int n, s; vector d; vector prev; vector visit; priority_queue, vector>, greater>> pq; public: Dijkstra(graph g_, int s_) : g(g_), n(g.size()), s(s_), d(n, 1000000000000000000), prev(n), visit(n, false) { d[s] = 0LL; pq.emplace(d[s], s); while (!pq.empty()) { int v = pq.top().second; pq.pop(); if (visit[v]) { continue; } visit[v] = true; for (auto e : g[v]) { int nv = e.to; long long nc = e.cost; if (d[nv] > d[v] + nc) { d[nv] = d[v] + nc; prev[nv] = e; pq.emplace(d[nv], nv); } } } } vector dists() { return d; } long long dist(int t) { return d[t]; } vector route(int t) { if (s == t || d[t] == 1000000000000000000) { return {}; } vector res; int cur = t; while (cur != s) { res.emplace_back(prev[cur]); cur = prev[cur].from; } reverse(res.begin(), res.end()); return res; } }; int main() { int n, m; cin >> n >> m; WeightedUnionFind uf(n); graph g(n); int s = -1, t = -1, id = -1; rep(i, m) { int u, v; lint w; cin >> u >> v >> w; u--; v--; if (!uf.same(u, v)) { uf.merge(v, u, w); g[u].add(u, v, w, i); g[v].add(v, u, w, i); } else { lint d = uf.diff(v, u); if (d == w) { uf.merge(v, u, w); g[u].add(u, v, w, i); g[v].add(v, u, w, i); } else if (d > w) { s = u; t = v; id = i; break; } else { s = v; t = u; id = i; break; } } } if (s >= 0) { auto r = Dijkstra(g, s).route(t); cout << r.size() + 1 << endl << s + 1 << endl; for (auto e : r) { cout << e.idx + 1 << " "; } cout << id + 1 << endl; return 0; } cout << -1 << endl; }