#include<bits/stdc++.h>
using namespace std;

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

template<typename T> T bpow(T x, size_t n) {
    if(n == 0) return T(1);
    else{auto t=bpow(x, n/2); t=t*t; return n%2 ? x*t : t;}
}
int m;
struct modular {
    int r; typedef modular mo;
    modular(): r(0) {}
    modular(int64_t rr): r(rr%m){if(r<0)r+=m;}
    mo inv() const {return bpow(*this, m - 2);}
    mo operator-()const{return r ? m - r : 0;}
    mo operator*(const mo &t)const{return (ll)r*t.r%m;}
    mo operator/(const mo &t)const{return *this*t.inv();}
    mo operator+=(const mo &t){
        r += t.r; if(r >= m) r -= m; return *this;}
    mo operator-=(const mo &t){
        r -= t.r; if(r < 0) r += m; return *this;}
    mo operator+(const mo &t)const{return mo(*this)+=t;}
    mo operator-(const mo &t)const{return mo(*this)-=t;}
    mo operator*=(const mo &t){return *this=*this*t;}
    bool operator==(const mo &t)const{return r==t.r;}
    bool operator>(const mo &t)const{return r>t.r;}
    bool operator<=(const double &t)const{return r<=int(t);}
    bool operator>(const double &t)const{return r>int(t);}
};
modular fabs(modular x){return x.r;}

typedef modular T; //oppure modular<mod>
typedef vector<T> vd;
const double eps = 1e-12;
vi col; //globale per ricavare il sottospazio
int solveLinear(vector<vd>& A, vd& b, vd& x) {
    int n = sz(A), m = sz(x), rank = 0, br, bc;
    if (n) assert(sz(A[0]) == m);
    col.resize(m); iota(all(col), 0);
    rep(i,0,n) {
        T v, bv = 0;
        rep(r,i,n) rep(c,i,m)
        if ((v = fabs(A[r][c])) > bv)
            br = r, bc = c, bv = v;
        if (bv <= eps) {
            rep(j,i,n) if (fabs(b[j]) > eps) return -1;
            break;
        }
        swap(A[i], A[br]); swap(b[i], b[br]);
        swap(col[i], col[bc]);
        rep(j,0,n) swap(A[j][i], A[j][bc]);
        bv = T(1)/A[i][i];
        rep(j,i+1,n) {
            T fac = A[j][i] * bv;
            b[j] -= fac * b[i];
            rep(k,i+1,m) A[j][k] -= fac*A[i][k];
        }
        rank++;
    }
    x.assign(m, T(0));
    for (int i = rank; i--;) {
        b[i] = b[i]/A[i][i];
        x[col[i]] = b[i];
        rep(j,0,i) {
            b[j] -= A[j][i] * b[i];
        }
    }
    return rank; // (multiple solutions if rank < m)
}

void solve(){
    int n,e;
    cin>>n>>e>>m;
    
    vd b,x;
    vector<vd> A;
    
    vector<array<int,4>> edges(e);
    vector ok(e,false),st(e,false);
    vd curr(e);
    vector grafo(n+1,vector<array<int,3>>());
    
    for(int i=0;i<e;i++){
        int u,v,x;
        cin>>u>>v>>x;
        b.push_back(x);
        edges[i]={u,v,(int)grafo[u].size(),(int)grafo[v].size()};
        grafo[u].push_back({v,false,i});
        grafo[v].push_back({u,false,i});
    }
    
    auto set = [&](int id,bool val){
        auto [u,v,ind1,ind2] = edges[id];
        grafo[u][ind1][1]=val;
        grafo[v][ind2][1]=val;
        curr[id]=val;
    };
    
    vector vis=vector(n,false);
    auto dfs = [&](auto &dfs,int nodo)->void{
        vis[nodo]=true;
        for(auto [to,act,id] : grafo[nodo]){
            if(!vis[to]){
                st[id]=true;
                set(id,true);
                dfs(dfs,to);
            }
        }
    };
    dfs(dfs,1);
    
    vector<int> cycle;
    auto findcycle = [&](auto &findcycle,int nodo,int last,int st)->bool{
        if(nodo==st)return true;
        
        bool res=false;
        for(auto [to,act,id] : grafo[nodo]){
            if(act && to!=last){
                if(findcycle(findcycle,to,nodo,st)){
                    cycle.push_back(id);
                    res=true;
                }
            }
        }
        return res;
    };
    
    for(int i=0;i<e;i++){
        if(!st[i]){
            //cout<<"processo "<<i<<"\n";
            cycle.clear();
            auto [u,v] = tie(edges[i][0],edges[i][1]);
            findcycle(findcycle,u,-1,v);
            
            set(i,true);
            for(auto j : cycle){
                //cout<<j<<" ";
                if(ok[j])continue;
                ok[j]=true;
                set(j,false);
                A.push_back(curr);
                set(j,true);
            }
            //cout<<"cicle \n";
            set(i,false);
        }
    }
    
    
    A.push_back(curr);
    int last=-1;
    /*
    for(int i=0;i<e;i++){
        if(!st[i]){
            cycle.clear();
            auto [u,v] = tie(edges[i][0],edges[i][1]);
            findcycle(findcycle,u,-1,v);
            
            set(i,true);
            
            bool ok=false;
            for(auto j : cycle){
                if(st[j]){
                    set(j,false);
                    ok=true;
                    break;
                }
            }
            if(!ok){
                set(cycle[0]==last ? cycle[1] : cycle[0],false);
            }
            
            A.push_back(curr);
            last=i;
        }
    }
    */
    while(A.size()<min(2*m,1300)){
        vector<int> opz;
        for(int i=0;i<e;i++){
            if(curr[i].r==0)opz.push_back(i);
        }
        if(opz.size()==0)break;
        
        int i = opz[rand()%opz.size()];
        
        cycle.clear();
        auto [u,v] = tie(edges[i][0],edges[i][1]);
        findcycle(findcycle,u,-1,v);
        
        set(i,true);
        
        bool ok=false;
        
        set(cycle[rand()%cycle.size()],false);
        
        A.push_back(curr);
        last=i;
    }
    /*
    for(auto i : A){
        for(auto j : i)cout<<j.r<<" ";
        cout<<"\n";
    }*/
    
    vector tmp = vector(e,vd(A.size()));
    
    for(int i=0;i<(int)A.size();i++){
        for(int j=0;j<(int)A[i].size();j++){
            tmp[j][i]=A[i][j];
        }
    }
    swap(A,tmp);
    x.resize(A[0].size());
    
    if(solveLinear(A,b,x)==-1){
        cout<<"-1\n";
    }else{
        cout<<x.size()<<"\n";
        for(int i=0;i<(int)x.size();i++){
            cout<<x[i].r<<" ";
            for(int j=0;j<(int)tmp[i].size();j++)if(tmp[i][j]==1){
                cout<<j+1<<" ";
            }
            cout<<"\n";
        }
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int t=1;
    //cin>>t;
    for(int i=1;i<=t;i++)solve();
    
    return 0;
}