#include<cstdio>
#include<assert.h>
using namespace std;
const int o=2010;
int n,m,p,h[o],cnt,w[o],s,fa[o],ans,Ans[o][o],tot,d[o],st[o],tp,St[o],Tp,ban,U[o],V[o],a[o][o],b[o];bool vis[o];
inline int qp(int b,int f){int res=1;for(;f;f>>=1,b=b*1ll*b%p) if(f&1) res=res*1ll*b%p;return res;}
struct Edge{int v,p,id;}e[o];
inline void ad(int U,int V,int ID){e[++cnt].v=V;e[cnt].p=h[U];e[h[U]=cnt].id=ID;}
void Dfs(int nw){
	vis[nw]=1;
	for(int i=h[nw];i;i=e[i].p) if(!vis[e[i].v])
		Ans[1][++tot]=fa[e[i].v]=e[i].id,w[e[i].id]=(w[e[i].id]+p-s)%p,d[e[i].v]=d[nw]+1,Dfs(e[i].v);
}
void ddfs(int nw){
	for(int i=h[nw];i;i=e[i].p) if(e[i].id-ban&&!vis[e[i].v]) vis[e[i].v]=1,Ans[ans][++tot]=e[i].id,ddfs(e[i].v);
}
inline void slv(int x,int w){
	Ans[++ans][0]=w;tot=0;
	for(int i=1;i<=n;++i) vis[i]=0;
	for(int i=1;i<=Tp;++i) vis[e[St[i]*2-1].v]=1,vis[e[St[i]*2].v]=1;
	for(int i=1;i<=Tp;++i) if(St[i]^x) Ans[ans][++tot]=St[i];
	ban=x;
	for(int i=1;i<=n;++i) if(vis[i]) ddfs(i);
}
inline void upd(int&u,int&v,int U,int V,int*arr,int&len,int*Arr,int Len){
	if(U&&(!u||d[u]+d[v]>d[U]+d[V])){
		u=U;v=V;len=Len;
		for(int i=1;i<=len;++i) arr[i]=Arr[i];
	}
}
void Slv(int x,int v,int*arr,int len){
	Tp=len;
	for(int i=1;i<=Tp;++i) St[i]=arr[i];
	slv(fa[v],w[x]);
	Ans[++ans][0]=p-w[x];
	for(int i=1;i<n;++i) Ans[ans][i]=Ans[ans-1][i];
	bool flg=0;
	for(int i=1;i<n;++i) if(Ans[ans][i]==x) Ans[ans][i]=fa[v],flg=1;
	assert(flg);
	w[fa[v]]=(w[fa[v]]+w[x])%p;w[x]=0; 
}
void dfs(int nw){
	st[++tp]=nw;
	for(int i=h[nw];i;i=e[i].p) if(fa[e[i].v]==e[i].id){
		dfs(e[i].v);
		if(U[e[i].v]^nw) upd(U[nw],V[nw],U[e[i].v],V[e[i].v],a[nw],b[nw],a[e[i].v],b[e[i].v]);
		if(w[e[i].id]&&U[e[i].v]) Slv(e[i].id,V[e[i].v],a[e[i].v],b[e[i].v]);
	}
	for(int i=h[nw],u,v;i;i=e[i].p) if(e[i].id-fa[nw]&&d[e[i].v]<d[nw]){
		v=st[d[u=e[i].v]+1];St[Tp=1]=e[i].id;
		for(int j=d[v];j<=d[nw];++j) St[++Tp]=fa[st[j]];
		if(w[e[i].id]&&u) Slv(e[i].id,v,St,Tp);
		upd(U[nw],V[nw],u,v,a[nw],b[nw],St,Tp);
	}
	--tp;
}
int main(){
	scanf("%d%d%d",&n,&m,&p);
	for(int i=1,u,v;i<=m;++i) scanf("%d%d%d",&u,&v,&w[i]),s=(s+w[i])%p,ad(u,v,i),ad(v,u,i);
	Ans[ans=1][0]=s=s*1ll*qp(n-1,p-2)%p;
	Dfs(d[1]=1);
	if(!s) --ans;
	dfs(1);
	for(int i=1;i<=m;++i) if(w[i]){printf("-1\n");return 0;}
	printf("%d\n",ans);
	for(int i=1,j;i<=ans;++i,putchar('\n')) for(printf("%d ",Ans[i][0]),j=1;j<n;++j) printf("%d ",Ans[i][j]);
	return 0;
}