#include<bits/stdc++.h>
#pragma GCC optimize(2)
#define int long long
#define inf 1000000000000000
using namespace std;
int n,m,u,v,w,tot,x,y,cnt,xx;
long long c;
const int mod=1000000009;
int rt[40010],vv[40010],id[40010],id2[40010],fa[40010],siz[40010];
long long ans;
struct Line{
	int u,v,w;
}l[80010]; 
struct Line2{
	int u,v;
	long long w;
}line[80010]; 
struct Val{
	int mn,hmn,nowid,hid;
};
struct Tag{
	int ad,had,id2;
};
struct Segtree{
	int lson,rson;
	Val val;
	Tag tag;
}tree[12000010];
vector<Line> a[40010],b[40010];
inline long long Qread(){
	char st;long long ans=0;st=getchar();
	while(!(st<='9'&&st>='0')) st=getchar();
	while(st<='9'&&st>='0') ans=(ans<<3)+(ans<<1)+(st^48),st=getchar();
	return ans;
}
int fnd(int x){
	if(fa[x]!=x) fa[x]=fnd(fa[x]);
	return fa[x];
}
Val DD(Val x,Val y){
	if(x.mn==-1) return y;
	if(y.mn==-1) return x;
	Val ans;
	if(x.hmn<y.hmn) ans.hmn=x.hmn,ans.hid=x.hid;
	else ans.hmn=y.hmn,ans.hid=y.hid;
	if(x.mn<y.mn) ans.mn=x.mn,ans.nowid=x.nowid;
	else ans.mn=y.mn,ans.nowid=y.nowid;
	return ans;
}
Val DM(Val x,Tag y){
	if(x.hmn<=y.had+x.mn||y.id2==0) return (Val){x.mn+y.ad,x.hmn,x.nowid,x.hid};
	return (Val){x.mn+y.ad,x.mn+y.had,x.nowid,x.nowid};
}
Tag MM(Tag x,Tag y){
	if(x.had<=y.had+x.ad) return (Tag){x.ad+y.ad,x.had,x.id2};
	return (Tag){x.ad+y.ad,y.had+x.ad,y.id2};
}
int new_node(int p){
	++tot;
	tree[tot]=tree[p];
	return tot;
}
void Pushdown(const int p){
	tree[p].lson=new_node(tree[p].lson);
	tree[p].rson=new_node(tree[p].rson);
	tree[tree[p].lson].val=DM(tree[tree[p].lson].val,tree[p].tag);
	tree[tree[p].lson].tag=MM(tree[tree[p].lson].tag,tree[p].tag);
	tree[tree[p].rson].val=DM(tree[tree[p].rson].val,tree[p].tag);
	tree[tree[p].rson].tag=MM(tree[tree[p].rson].tag,tree[p].tag);
	tree[p].tag=(Tag){0,0,0};
	return;
} 
void Build(int &p,const int l,const int r){
	p=++tot;
	if(l==r){
		tree[p].val=(Val){vv[l],vv[l],l,l};return;
	}
	const int mid=(l+r)>>1;
	Build(tree[p].lson,l,mid);
	Build(tree[p].rson,mid+1,r);
	tree[p].val=DD(tree[tree[p].lson].val,tree[tree[p].rson].val);
	return;
}
void Modify(int &p,const int L,const int R,const int l,const int r,const Tag tag){
	p=new_node(p);
	if(L<=l&&r<=R){
		tree[p].val=DM(tree[p].val,tag);
		tree[p].tag=MM(tree[p].tag,tag);
		return;
	}
	if(tree[p].tag.id2||tree[p].tag.ad||tree[p].tag.had) Pushdown(p);
	const int mid=(l+r)>>1;
	if(L<=mid) Modify(tree[p].lson,L,R,l,mid,tag);
	if(R>mid) Modify(tree[p].rson,L,R,mid+1,r,tag);
	tree[p].val=DD(tree[tree[p].lson].val,tree[tree[p].rson].val);
	return;
}
void Del(int &p,const int L,const int R,const int l,const int r){
	p=new_node(p);
	if(L<=l&&r<=R){
		tree[p].val=(Val){inf,inf,0,0};
		return;
	}
	if(tree[p].tag.id2||tree[p].tag.ad||tree[p].tag.had) Pushdown(p);
	const int mid=(l+r)>>1;
	if(L<=mid) Del(tree[p].lson,L,R,l,mid);
	if(R>mid) Del(tree[p].rson,L,R,mid+1,r);
	tree[p].val=DD(tree[tree[p].lson].val,tree[tree[p].rson].val);
	return;
}
Val Query(int p,const int L,const int R,const int l,const int r,Tag tag){
	if(L<=l&&r<=R){
		return DM(tree[p].val,tag);
	}
	if(tree[p].tag.id2||tree[p].tag.ad||tree[p].tag.had) tag=MM(tree[p].tag,tag);
	const int mid=(l+r)>>1;Val ans=(Val){-1,-1,-1,-1};
	if(L<=mid) ans=DD(ans,Query(tree[p].lson,L,R,l,mid,tag));
	if(R>mid) ans=DD(ans,Query(tree[p].rson,L,R,mid+1,r,tag));
	return ans;
}
void Addline(int u,int v,long long w){
	line[++cnt].u=u,line[cnt].v=v,line[cnt].w=w;
	return;
}
int xxx;
void solve(int l,int r){
	if(l==r) return;
	int x=id[l],y=id[r];
	if(x>y) swap(x,y);
	Val w=(Val){-1,-1,-1,-1};
	if(x>1) w=DD(w,Query(rt[x-1],x,y-1,1,n,(Tag){0,0,0}));
	w=DD(w,Query(rt[y+n],x,y-1,1,n,(Tag){0,0,0}));
	Addline(l,r,2*c+(long long)w.hmn);
	solve(l,w.hid);
	solve(w.hid+1,r); 
	return;
}
bool cmp(Line2 x,Line2 y){
	return x.w>y.w;
}
bool cmpw(Line x,Line y){
	return x.w>y.w;
}
signed main()
{
//	freopen("destory.in","r",stdin);
//	freopen("destory.out","w",stdout);
	n=Qread(),m=Qread();c=1e9;
	for(int i=1;i<=m;i++){
		u=Qread(),v=Qread(),w=Qread();
		if(u>v) swap(u,v);
		a[u].push_back((Line){u,v-1,-w});
		a[u].push_back((Line){v,n,w});
		a[v].push_back((Line){v,n,-w});
		
		b[v-1].push_back((Line){u,v-1,-w});
		if(u-1) b[v-1].push_back((Line){1,u-1,w});
		if(u-1) b[u-1].push_back((Line){1,u-1,-w});
		l[i].u=u,l[i].v=v,l[i].w=w;
	}
	for(int i=1;i<=n;i++){
		sort(a[i].begin(),a[i].end(),cmpw);
		sort(b[i].begin(),b[i].end(),cmpw);
	}
	for(int i=1;i<=m;i++){
		vv[l[i].u]+=l[i].w;
		vv[l[i].v]-=l[i].w;
	}
	for(int i=0;i<a[1].size();++i){
		vv[a[1][i].u]+=a[1][i].w;
		vv[a[1][i].v+1]-=a[1][i].w;
	}
	for(int i=1;i<=n;i++){
		vv[i]+=vv[i-1];
	}
	vv[1]=inf;
	xx=1,Build(rt[1],1,n);
	for(int i=2;i<=n;i++){
		Del(rt[i-1],i-1,i-1,1,n);
		rt[i]=rt[i-1];
		for(int j=0;j<a[i].size();++j){
			Modify(rt[i],a[i][j].u,a[i][j].v,1,n,(Tag){a[i][j].w,a[i][j].w,i});
		}
	}
	for(int i=1;i<=n;i++) vv[i]=0;
	for(int i=1;i<=m;i++){
		vv[l[i].u]+=l[i].w;
		vv[l[i].v]-=l[i].w;
	}
	for(int i=0;i<b[n].size();++i){
		vv[b[n][i].u]+=b[n][i].w;
		vv[b[n][i].v+1]-=b[n][i].w;
	}
	for(int i=1;i<=n;i++) vv[i]+=vv[i-1];
	vv[n]=inf;
	xx=n,Build(rt[n<<1],1,n);
	for(int i=n-1;i>=1;i--){
		Del(rt[n+i+1],i+1,i+1,1,n);
		rt[n+i]=rt[n+i+1];
		for(int j=0;j<b[i].size();++j){
			Modify(rt[n+i],b[i][j].u,b[i][j].v,1,n,(Tag){b[i][j].w,b[i][j].w,i});
		}
	}
	Del(rt[n],n,n,1,n);
	Del(rt[n+1],1,1,1,n);
	for(int i=1;i<=n;i++) id[i]=i,fa[i]=i,siz[i]=1;
	solve(1,n);
	sort(line+1,line+cnt+1,cmp);
	for(int i=1;i<=cnt;i++){
		x=fnd(line[i].u),y=fnd(line[i].v);
		ans=(ans+siz[x]%mod*siz[y]%mod*(line[i].w%mod))%mod;
		siz[x]+=siz[y];
		fa[y]=x;
	}
	printf("%lld",ans);
	return 0;
}