#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
//#define ll __int128
//#define int long long
#define ci const int
#define rg int
#define ld long double
#define mid ((L+R)>>1)
#define fo(i,l,r) for(ll i=(l);i<=(r);++i)
#define fd(i,l,r) for(ll i=(l);i>=(r);--i)
#define fu(i,l,r) for(ll i=(l);i<(r);++i)
#define gcd __gcd
#define P(x) __builtin_popcountll(x)
#define W(x) __builtin_ctzll(x)
#define lowbit(x) (x&-x)
using namespace std;
ci N=5e6+5,mod=1e9+9;
const ll inf=1e9;
bool ST;
ll ksm(ll a,ll b=mod-2)
{
	ll ans=1;
	while(b)
	{
		if(b&1)ans=ans*a%mod;
		a=a*a%mod;
		b>>=1;
	}
	return ans;
}
void _(ll &a,ll b){a=(a+b)%mod;}
inline ll read(){ll u,f=1;char o;while((o=getchar())<48||o>57)if(o==45)f=-1;u=(o^48);while((o=getchar())>=48&&o<=57)u=(u<<1)+(u<<3)+(o^48);return u*f;}
void write(ll x){if(x<0)putchar(45),x=-x;if(x>9)write(x/10);putchar(x%10+48);}
mt19937_64 rad(chrono::steady_clock::now().time_since_epoch().count());
ll n,m,q,C;
struct node
{
	int x,y,val;
};
bool operator < (const node x,const node y)
{
	return x.val>y.val;
}
node min(const node x,const node y)
{
	if(x.val<y.val)return x;
	return y;
}
struct segment
{
	vector<node>use[N];
	int s,l[N],r[N],rt[N];int lazysum[N],lazy[N];node lastminn[N],minn[N];
	int copy(int x)
	{
		l[++s]=l[x],r[s]=r[x],lazysum[s]=lazysum[x],minn[s]=minn[x],lastminn[s]=lastminn[x],lazy[s]=lazy[x];
		return s;
	}
	void push(ci x,ci sum1,ci lazy1)
	{
		lastminn[x]=min(lastminn[x],{0,minn[x].y,minn[x].val+lazy1});
		minn[x].val+=sum1;
		lazy[x]=min(lazy[x],lazy1+lazysum[x]);
		lazysum[x]+=sum1;
	}
	void pushdown(ci x)
	{
		if(lazysum==0)return;
		l[x]=copy(l[x]),r[x]=copy(r[x]);
		push(l[x],lazysum[x],lazy[x]);
		push(r[x],lazysum[x],lazy[x]);
		lazysum[x]=0,lazy[x]=inf;
	}
	void upd(ci x)
	{
		minn[x]=min(minn[l[x]],minn[r[x]]);
		lastminn[x]=min(lastminn[l[x]],lastminn[r[x]]);
	}
	void build(ci x,ci L,ci R)
	{
		lazy[x]=inf;
		if(L==R)
		{
			lastminn[x]=minn[x]={0,L,qz[L]};
			return;
		}
		l[x]=++s,r[x]=++s;
		build(l[x],L,mid);
		build(r[x],mid+1,R);
		upd(x);
//		cout<<minn[x].y<<' '<<minn[x].val<<'\n';
	}
	void change(ci x,ci L,ci R,ci o,ci o1,ci val)
	{
		if(o<=L&&R<=o1)
		{
			push(x,val,val);
			return;
		}
		if(R<o||o1<L)return;
		pushdown(x);
		change(l[x],L,mid,o,o1,val);
		change(r[x],mid+1,R,o,o1,val);
		upd(x);
	}
	node cha(ci x,ci L,ci R,ci o,ci o1)
	{
//		cout<<x<<' '<<L<<' '<<R<<' '<<o<<' '<<o1<<' '<<minn[x].val<<'\n'; 
		if(o<=L&&R<=o1)
		{
			return lastminn[x];
		}
		if(R<o||o1<L)return {0,0,inf};
		pushdown(x);
		return min(cha(l[x],L,mid,o,o1),cha(r[x],mid+1,R,o,o1));
	}
	int qz[N];
	void init()
	{
		fo(i,1,n)
		{
			rt[i]=copy(rt[i-1]);
			if(i==1)
			{
				for(auto d:use[i])
				{
					qz[d.x]+=d.val;
					qz[d.y+1]-=d.val;
				}
				fo(i,1,n)qz[i]+=qz[i-1];
				build(1,1,n);
			}
			else
			{
				sort(use[i].begin(),use[i].end());
				for(auto d:use[i])
				{
					change(rt[i],1,n,d.x,d.y,d.val);
				}
			}
		}
	}
}t0,t1;//贴1，贴n反x 
void add(int x,int xx,int y,int yy,ci val)
{
	if(x>xx||y>yy)return;
//	cout<<x<<' '<<xx<<' '<<y<<' '<<yy<<' '<<val<<'\n';
	t0.use[x].push_back({y,yy,val});
	t0.use[xx+1].push_back({y,yy,-val});
	t1.use[n-xx+1].push_back({y,yy,val});
	t1.use[n-x+2].push_back({y,yy,-val});
}
vector<node>edge;
void solve(int x,int y)
{
	if(x==y)return;
	node now1={0,0,inf},now2={0,0,inf};
	if(x-1)now1=t0.cha(t0.rt[x-1],1,n,x,y-1);
	now2=t1.cha(t1.rt[n-y+1],1,n,x,y-1);
	now1=min(now1,now2);
//	cout<<now1.val<<' '<<now2.val<<'\n';
	edge.push_back({x,y,now1.val});
//	cout<<x<<' '<<y<<' '<<now1.y<<' '<<now1.val<<'\n'; 
	solve(x,now1.y),solve(now1.y+1,y);
}
int f[N];ll siz[N];
int find(int x)
{
	if(f[x]==x)return x;
	return f[x]=find(f[x]);
}
bool ED;int main()
{cerr<<"memory:"<<(&ST-&ED)/1048576.0<<'\n';
	int T=1;int id=1;
	while(T--)
	{
		n=read(),m=read();C=1e9;
		fo(i,1,m)
		{
			ll x=read(),y=read(),val=read();
			if(x>y)swap(x,y);
			add(1,x-1,x,y-1,val);
			add(y,n,x,y-1,val);
			add(x,y-1,1,x-1,val);
			add(x,y-1,y,n,val);
		}
		t0.init(),t1.init();
		solve(1,n);
		ll ans=n*(n-1)%mod*C%mod;
		fo(i,1,n)f[i]=i,siz[i]=1;
		sort(edge.begin(),edge.end());
		for(auto d:edge)
		{
			int x=find(d.x),y=find(d.y);
			_(ans,siz[x]*siz[y]%mod*d.val);
			f[x]=y;
			siz[y]+=siz[x];
		}
		cout<<ans*2%mod<<'\n';
	}
	return 0;
}