ROAD

#include <iostream>
#include <cstdio>
#include <vector>
#include <map>
#include <queue>
#include <unordered_map>
#define task "ROAD"
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;

const int N = 2e5 + 2;
int n, m;
int u[N], v[N], c[N];
vector<int> adj[N], ans;
unordered_map<int, pair<int, int>> par[N];


void Read()
{
    cin >> n >> m;
    for(int i = 1; i <= m; ++i)
    {
        cin >> u[i] >> v[i] >> c[i];
        adj[u[i]].push_back(i);
    }
}

int BFS(int x)
{
    struct Tque
    {
        int col, v;
        Tque(int v = 0, int col = 0)
        {
            this->v = v;
            this->col = col;
        }
    };
    queue<Tque> s;
    for(auto i : adj[x])
        if(par[v[i]].empty() ||
                (par[v[i]].size() == 1 && c[par[v[i]].begin()->first] != c[i]))
        {
            s.emplace(i, c[i]);
            par[v[i]][i] = {x, 0};
        }
    while(s.size())
    {
        Tque top = s.front();
        s.pop();
        for(auto i : adj[v[top.v]])
            if(c[i] != c[top.v])
            {
                if(v[i] != x)
                {
                    if((par[v[i]].empty() ||
                            (par[v[i]].size() == 1 && c[par[v[i]].begin()->first] != c[i])))
                    {
                        s.emplace(i, top.col);
                        par[v[i]][i] = {v[top.v], top.v};
                    }
                }
                else
                {
                    if(c[i] != top.col)
                    {
                        par[x][i] = {v[top.v], top.v};
                        return i;
                    }
                }
            }
    }
    return -1;
}

void Trace(int v, int j, const int &x, const int &vv)
{
    if(v == vv && j != x)
        return;
    Trace(par[v][j].first, par[v][j].second, x, vv);
    ans.push_back(j);
}

void Sub2()
{
    for(int i = 1; i <= n; ++i)
    {
        int v = BFS(i);
        if(v != -1)
        {
            Trace(i, v, v, i);
            cout << ans.size() << "\n";
            for(auto j : ans)
                cout << j << " ";
            return;
        }
        for(int i = 1; i <= n; ++i)
            par[i].clear();
    }
    cout << -1;
}

void Sub3()
{
    for(int i = 1; i <= n; ++i)
    {
        int v = BFS(i);
        if(v != -1)
        {
            Trace(i, v, v, i);
            cout << ans.size() << "\n";
            for(auto j : ans)
                cout << j << " ";
            return;
        }
        for(int i = 1; i <= n; ++i)
            par[i].clear();
    }
    cout << -1;
}

int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    if(fopen(task".INP", "r"))
    {
        freopen(task".INP", "r", stdin);
        freopen(task".OUT", "w", stdout);
    }
    Read();
    if(m <= 5000)
        Sub2();
    else
        Sub3();
}