#include<bits/stdc++.h>
#define MOD 1000002013
using namespace std;
struct item{
long long count;
long long pos;
char lr;
bool operator<(item b)const
{
if(this->pos!=b.pos)
return this->pos<b.pos;
else
return this->lr<b.lr;
}
item(long long count,long long pos,char lr)
{
this->count=count;
this->pos=pos;
this->lr=lr;
}
item(){}
};
int n,m;
item data[2010];
long long cal(long long o,long long e,long long p)
{
long long l=e-o;
return (((n+n-l+1)*l/2)%MOD) * p %MOD;
}
long long solve()
{
stack<item> stk;
long long ans=0;
for(int i=0;i<m*2;i++)
{
if(data[i].lr=='(')
{
stk.push(data[i]);
}
else
{
long long left=data[i].count;
while(left!=0)
{
long long change=min(left,stk.top().count);
ans+=cal(stk.top().pos,data[i].pos,change);
ans%=MOD;
stk.top().count-=change;
left-=change;
if(stk.top().count==0)
stk.pop();
}
}
}
return ans;
}
int main()
{
int T;
cin>>T;
for(int no=1;no<=T;no++)
{
memset(data,0,sizeof data);
cin>>n>>m;
long long origin=0,swapped=0;
for(int i=0;i<m;i++)
{
long long o,e,p;
cin>>o>>e>>p;
origin+=cal(o,e,p);
origin%=MOD;
data[i*2]=item(p,o,'(');
data[i*2+1]=item(p,e,')');
}
sort(data,data+m*2);
swapped=solve();
printf("Case #%d: %lld\n",no,(origin-swapped+MOD)%MOD);
}
}
