题目大意：有一个n的个点的无向边权图，A和B两个人要从1号点去往n号点，每一轮，他们会轮流选择下一步要走的一条边，然后两个人一起走过去，A先选，他们每次选的路一定是到1到n的最短路上的一条边，最后到n时轮到谁选就算谁输，问谁能赢
2<=n<=1e5；2<=m<=2e5;1<=w[i]<=1e9
思路：因为直走最短路，所以我们把所有在最短路上的边都要选出来，建成新图，为此，首先用dijkstra求出1到n的最短路的长度，然后我们从n开始bfs，遍历相邻边，如果这条边的边权加上1到这条边起点的最短路距离等于1到这条边终点的最短路距离，那么就把这条边加到新图中，最后就会形成一个包含1到n的所有最短路的DAG。
然后考虑sg的转移，显然当他们在n点时，先手必败，令sg[n]=0，然后因为新图是无向图，所以按照常规树上博弈的方法转移，sg[u]=MEX(sg[v1],sg[v2]...)，但因为不是树而是图，所以要记忆化一下，避免重复遍历
#include<bits/stdc++.h>
//#include<__msvc_all_public_headers.hpp>
using namespace std;
typedef long long ll;
const ll MOD = 1e9 + 7;
const int N = 1e5 + 10, M = 2e5 + 10;
const ll INF = 1e18;
struct Edge
{
int u, v, next;
ll w;
}e[M*2];//链式前向星存图
struct node
{//优先队列中存储的点的编号和最短路
int id;
ll dis;
bool operator<(const node& a)const
{
return dis > a.dis;
}//因为我们要小的先出队，所以要把小于号重载为大于
node(int a, ll b)
{
id = a, dis = b;
}
};
int head[N], cnt = 0;
void addedge(int u, int v, ll w)
{//这里边的起点也要记录
e[++cnt].v = v;
e[cnt].u = u;
e[cnt].w = w;
e[cnt].next = head[u];
head[u] = cnt;
}
int n, m;
ll dis[N];
bool done[N];
ll fid;
ll sg[N];
set<int>ins;
vector<int>g[N];
bool vis[N];
void bfs()
{//建立新图
queue<int>q;
q.push(n);//从n开始bfs
while (!q.empty())
{
int u = q.front();
q.pop();
if (vis[u])
continue;
vis[u] = 1;//避免重复遍历
for (int i = head[u]; ~i; i = e[i].next)
{
int v = e[i].v;
ll w = e[i].w;
if (dis[v] + w == dis[u])
{//这个边是想要的边
g[v].push_back(u);
q.push(v);
}
}
}
}
void dijkstra()
{
int s = 1;
for (int i = 1; i <= n; i++)
{
dis[i] = INF;//初始化到所有点的最短路为一极大值
done[i] = 0;//判断每个点是否在集合A里
}
dis[s] = 0;
priority_queue<node>q;
q.push(node(s, dis[s]));
while (!q.empty())
{
node u = q.top();
q.pop();
if (done[u.id])
{//已在集合A中的点说明已经找到最短路了
continue;
}
done[u.id] = 1;
for (int i = head[u.id]; ~i; i = e[i].next)
{
int v = e[i].v;
ll w = e[i].w;
if (done[v])
{
continue;
}//避免回头访问到处理过的点
if (dis[v] > w + u.dis)
{
dis[v] = w + u.dis;//维护最短路
q.push(node(v, dis[v]));
}
}
}
}
int dfs2(int u)
{//求sg
if (sg[u] != -1)
{//记忆化
return sg[u];
}
set<int>temp;
for (int i = 0; i < g[u].size(); i++)
{// 遍历子节点
int v = g[u][i];
temp.insert(dfs2(v));
}
int now = 0;
for (set<int>::iterator it = temp.begin(); it != temp.end(); it++)
{//找MEX
if (*it == now)
{
now++;
}
else
{
sg[u] = now;
return sg[u];;
}
}
sg[u] = now;
return sg[u];
}
void init()
{
cnt = 0;
for (int i = 1; i <= n; i++)
{
head[i] = -1;
g[i].clear();
sg[i] = -1;
vis[i] = 0;
}
ins.clear();
}
void solve()
{
cin >> n;
init();
cin >> m;
for (int i = 1; i <= m; i++)
{
ll u, v, w;
cin >> u >> v >> w;
addedge(u, v, w);
addedge(v, u, w);
}
dijkstra();
fid = dis[n];
bfs();
sg[n] = 0;
dfs2(1);
if (!sg[1])
{//sg=0这里表示先手必输
cout << "Little I is the winner.\n";
return;
}
cout << "Little M is the winner.\n";
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int t;
cin >> t;
//t = 1;
while (t--)
{
solve();
}
return 0;
}
//6 7
//1 2 1
//2 3 1
//2 4 2
//3 4 1
//4 5 1
//5 6 1
//4 6 2
//2 1
//1 2 1
//3 3
//1 2 1
//2 3 1
//1 3 3
//8 9
//1 2 1
//2 3 1
//2 4 2
//3 4 1
//4 5 1
//5 8 1
//4 8 2
//1 7 2
//1 6 1