var
g,mo,next,v,f,w:array[0..80000]of longint;
n,i,j,m,t,t0,tt,a,b,c,ans:longint;

procedure dfs(x:longint);
var
e,y:longint;
begin
    e:=g[x];
    if ans=-1 then exit;
    while e<>0 do begin
        y:=mo[e];
        if f[y]<>0 then begin
            case v[e] of
            0:if w[y]<>w[x] then begin
                  ans:=-1;exit;
              end;
            1:if w[y]=w[x] then  begin
                  ans:=-1;exit;
              end;
              end;
        end
        else begin
            f[y]:=x;
            case v[e] of
            0:w[y]:=w[x];
            1:w[y]:=(w[x]+1) mod 2;
            end;
            dfs(y);
        end;
        e:=next[e];
    end;
end;

function father(x:longint):longint;
begin
    if f[x]=x then exit(x);
    f[x]:=father(f[x]);
    exit(f[x]);
end;

begin
assign(input,'line.in');reset(input);
assign(output,'line.out');rewrite(output);
    read(t0);
    for tt:=1 to t0 do begin
        fillchar(f,sizeof(f),0);
        fillchar(g,sizeof(g),0);
        t:=0; ans:=2;
        read(n,m);
        for i:=1 to m do begin
            read(a,b,c);
            inc(t);
            next[t]:=g[a];g[a]:=t;mo[t]:=b;v[t]:=c;
            inc(t);
            next[t]:=g[b];g[b]:=t;mo[t]:=a;v[t]:=c;
        end;
        for i:=1 to n do
        if f[i]=0 then begin
        f[i]:=i;w[i]:=1;
        dfs(i);
        end;
        if ans>=0 then begin
            a:=father(n);
            if a=1 then begin
                if w[n]=w[1] then writeln(0)
                else writeln(1);
            end
            else writeln(2);
        end
        else writeln('No Answer');
    end;
close(input);close(output);
end.