var
  time,x,i,j,y,z,t,n,m:longint;
  yes:boolean;
  g,w:array[0..500,0..500]of longint;
  d:array[0..5000]of longint;
  v:array[0..5000]of boolean;

procedure go(k:longint);
var
  j,i:longint;
begin
  for i:=1 to n do
  if g[k,i]>-1 then
  begin
    v[i]:=true;
    if d[i]=-1 then
    begin
      d[i]:=d[k]+g[k,i];
      go(i);
    end
    else begin
      if (d[i]-d[k]-g[k,i]) mod 2=1 then
      begin
        yes:=false;
        exit;
      end;
    end;
  end;
end;

begin
  assign(input,'line.in'); reset(input);
  assign(output,'line.out'); rewrite(output);
  readln(t);
  for time:=1 to t do
  begin
    readln(n,m);
    for i:=1 to n do
    begin
      d[i]:=-1;
      v[i]:=false;
      for j:=0 to n do
      begin
        g[i,j]:=-1;
      end;
    end;
    for i:=1 to m do
    begin
      readln(x,y,z);
      g[x,y]:=z;
      g[y,x]:=z;
    end;
    d[1]:=0;
    v[1]:=true;
    yes:=true;
    go(1);
    if not yes then
    begin
      writeln('No Answer');
      continue;
    end;
    if d[n]=-1 then
    begin
      for i:=2 to n do
      if not v[i] then
      begin
        v[i]:=true;
        d[i]:=0;
        go(i);
      end;
      if not yes then
      begin
        writeln('No Answer');
        continue;
      end
      else begin
        writeln(2);
        continue;
      end;
    end;
    if (d[n]-d[1]) mod 2=0 then writeln(0)
    else writeln(1);
  end;
  close(input);
  close(output);
end.