#include<bits/stdc++.h>
//#pragma GCC optimize(3,"Ofast","inline")
//#define int long long
#define i128 __int128
#define ll long long
#define ull unsigned long long
#define uint unsigned int
#define ld double
#define PII pair<int,int>
#define INF 0x3f3f3f3f
#define INFLL 0x3f3f3f3f3f3f3f3f
#define chkmax(a,b) a=max(a,b)
#define chkmin(a,b) a=min(a,b)
#define rep(k,l,r) for(int k=l;k<=r;++k)
#define per(k,r,l) for(int k=r;k>=l;--k)
#define cl(f,x) memset(f,x,sizeof(f))
#define pcnt(x) __builtin_popcount(x)
#define lg(x) (31-__builtin_clz(x))
using namespace std;
void file_IO() {
//	system("fc .out .ans");
	freopen("ex_destory5.in","r",stdin);
	freopen("destory.out","w",stdout);
}
bool M1;
template<int p>
struct mint {
	int x;
	mint() {
		x=0;
	}
	mint(int _x) {
		x=_x;
	}
	mint(ll _x) {
		x=_x%p;
	}
	friend mint operator + (mint a,mint b) {
		return a.x+b.x>=p? a.x+b.x-p:a.x+b.x;
	}
	friend mint operator - (mint a,mint b)  {
		return a.x<b.x? a.x-b.x+p:a.x-b.x;
	}
	friend mint operator * (mint a,mint b) {
		return 1ll*a.x*b.x%p;
	}
	friend mint operator ^ (mint a,ll b) {
		mint res=1,base=a;
		while(b) {
			if(b&1)
				res*=base;
			base*=base; b>>=1;
		}
		return res;
	}
	friend mint operator ~ (mint a) {
		return a^(p-2);
	}
	friend mint operator / (mint a,mint b) {
		return a*(~b);
	}
	friend mint & operator += (mint& a,mint b) {
		return a=a+b;
	}
	friend mint & operator -= (mint& a,mint b) {
		return a=a-b;
	}
	friend mint & operator *= (mint& a,mint b) {
		return a=a*b;
	}
	friend mint & operator /= (mint& a,mint b) {
		return a=a/b;
	}
	friend mint operator ++ (mint& a) {
		return a+=1;
	}
	friend mint operator -- (mint& a) {
		return a-=1;
	}
};
const int MOD=1e9+9;
#define mint mint<MOD>
const int N=23333+5;
int a[N];
struct SGT {
	static const int M=1e7+5;
	struct node {
		int lson,rson,tag,tagmn;
		PII val,valmn;
	}; node tree[M];
	#define ls(k) tree[k].lson
	#define rs(k) tree[k].rson
	int p;
	int new_node(int k) {
		tree[++p]=tree[k];
		return p;
	}
	void push_up(int k) {
		tree[k].val=min(tree[ls(k)].val,tree[rs(k)].val);
		tree[k].valmn=min(tree[ls(k)].valmn,tree[rs(k)].valmn);
	}
	void build(int &k,int l,int r) {
		k=new_node(k);
		if(l==r) {
			tree[k].valmn=tree[k].val=make_pair(a[l],l);
			return;
		}
		int mid=(l+r)>>1;
		build(ls(k),l,mid);
		build(rs(k),mid+1,r);
		push_up(k);
	}
	void upd(int &k,int val,int valmn) {
		k=new_node(k);
		PII t=tree[k].val;
		t.first+=valmn;
		chkmin(tree[k].valmn,t);
		chkmin(tree[k].tagmn,tree[k].tag+valmn);
		tree[k].val.first+=val;
		tree[k].tag+=val;
	}
	void push_down(int k) {
		int &t=tree[k].tag,&tmn=tree[k].tagmn;
		if(t||tmn) {
			upd(ls(k),t,tmn);
			upd(rs(k),t,tmn);
			t=tmn=0;
		}
	}
	void update(int &k,int l,int r,int ql,int qr,int val) {
		if(ql>qr)
			return;
		if(ql<=l&&r<=qr) {
			upd(k,val,min(val,0));
			return;
		}
		k=new_node(k);	
		push_down(k);
		int mid=(l+r)>>1;
		if(ql<=mid)
			update(ls(k),l,mid,ql,qr,val);
		if(qr>=mid+1)
			update(rs(k),mid+1,r,ql,qr,val);
		push_up(k);
	}
	PII query(int k,int l,int r,int ql,int qr) {
		if(ql>qr)
			return make_pair(INF,0);
		if(ql<=l&&r<=qr)
			return tree[k].valmn;
		push_down(k);
		PII res=make_pair(INF,0);
		int mid=(l+r)>>1;
		if(ql<=mid)
			chkmin(res,query(ls(k),l,mid,ql,qr));
		if(qr>=mid+1)
			chkmin(res,query(rs(k),mid+1,r,ql,qr));
		return res;
	}
	#undef ls
	#undef rs
}; SGT T;
struct DSU {
	int fa[N],siz[N];
	void init(int n) {
		rep(i,1,n) {
			fa[i]=i;
			siz[i]=1;
		}
	}
	int find(int x) {
		if(fa[x]!=x)
			fa[x]=find(fa[x]);
		return fa[x];
	}
	bool same(int u,int v) {
		return find(u)==find(v);
	}
	void merge(int u,int v) {
		u=find(u); v=find(v);
		if(u!=v) {
			fa[u]=v;
			siz[v]+=siz[u];
		}
	}
	int get_val(int x) {
		return siz[find(x)];
	}
}; DSU S;
struct node {
	int u,v,w;
	bool operator < (const node &tmp) const {
		return w>tmp.w;
	}
}; vector<node> edge;
int n,m,q,rtpre[N],rtsuf[N],d[N];
struct node1 {
	int l,r,val;
	bool operator < (const node1 &tmp) const {
		return val>tmp.val;
	}
}; vector<node1> vecpre[N],vecsuf[N];
void upd_pre(int xl,int xr,int yl,int yr,int val) {
	if(xl>xr||yl>yr)
		return;
	vecpre[xl].push_back({yl,yr,val});
	vecpre[xr+1].push_back({yl,yr,-val});
}
void upd_suf(int xl,int xr,int yl,int yr,int val) {
	if(xl>xr||yl>yr)
		return;
	vecsuf[xr].push_back({yl,yr,val});
	vecsuf[xl-1].push_back({yl,yr,-val});
}
void query_pre(int xr,int yl,int yr,int &p,int &w) {
	if(xr<1||yl>yr)
		return;
	PII val=T.query(rtpre[xr],1,n,yl,yr);
	if(val.first<w) {
		w=val.first;
		p=val.second;
	}
}
void query_suf(int xl,int yl,int yr,int &p,int &w) {
	if(xl>n||yl>yr)
		return;
	PII val=T.query(rtsuf[xl],1,n,yl,yr);
	if(val.first<w) {
		w=val.first;
		p=val.second;
	}
}
void solve(int l,int r) {
	if(l>=r)
		return;
	int p=0,w=INF;
	query_pre(l,l+1,r,p,w);
	query_suf(r+1,l+1,r,p,w);
//	fprintf(stderr,"%d -> %d get (%d,%d)\n",l,r,p,w);
	edge.push_back({l,r,w});
	solve(l,p-1);
	solve(p,r);
}
void solve() {
	int val;
	scanf("%d%d%d",&n,&m,&val);
	while(m--) {
		int u,v,w;
		scanf("%d%d%d",&u,&v,&w);
		if(u>v)
			swap(u,v);
		upd_pre(1,u,u+1,v,w);
		upd_suf(u+1,v,1,u,w);
		upd_pre(u+1,v,v+1,n,w);
		upd_suf(v+1,n,u+1,v,w);
	}
	rep(i,1,n) {
		sort(vecpre[i].begin(),vecpre[i].end());
		sort(vecsuf[i].begin(),vecsuf[i].end());
	}
	rep(i,1,n)
		a[i]=0;
	for(auto x:vecpre[1]) {
		a[x.l]+=x.val;
		a[x.r+1]-=x.val;
	}
	rep(i,1,n)
		a[i]+=a[i-1];
	T.build(rtpre[1],1,n);
	rep(i,2,n) {
		rtpre[i]=rtpre[i-1];
		for(auto x:vecpre[i])
			T.update(rtpre[i],1,n,x.l,x.r,x.val);
	}
	rep(i,1,n)
		a[i]=0;
	for(auto x:vecsuf[n]) {
		a[x.l]+=x.val;
		a[x.r+1]-=x.val;
	}
	rep(i,1,n)
		a[i]+=a[i-1];
	T.build(rtsuf[n],1,n);
	per(i,n-1,1) {
		rtsuf[i]=rtsuf[i+1];
		for(auto x:vecsuf[i])
			T.update(rtsuf[i],1,n,x.l,x.r,x.val);
	}
	solve(1,n);
	sort(edge.begin(),edge.end());
	S.init(n);
	mint res=0;
	for(auto x:edge) {
		int u=x.u,v=x.v,w=x.w;
		res+=mint(1ll*w+2ll*val)*mint(S.get_val(u))*mint(S.get_val(v));
		S.merge(u,v);
	}
	res*=2;
	printf("%d\n",res.x);
}
bool M2;
signed main() {
	file_IO();
	int testcase=1;
	//scanf("%d",&testcase);
	while(testcase--)
		solve();
	fprintf(stderr,"used time = %ldms\n",1000*clock()/CLOCKS_PER_SEC);
	fprintf(stderr,"used memory = %lldMB\n",(&M2-&M1)/1024/1024);
	return 0;
}