这题应该算是本题中最难的一题了。不过如果搜索和剪枝的基础过关，应该也是很好做的。下面给出较简单的算法：

首先，对于每个人，都是只有是内奸或不是内奸两种可能。那么就枚举吧！设一个过程 search(n) 表示枚举第 $n$ 个人的身份，因为要按升序输出所有可能，所以先设他是内奸，然后从 $1$ 到 $n$ for 一次，看是否出现与前面的矛盾的。比如说，前面有个人已经假设不是内奸了（即之前的search过程假设），而这个人又说 $n$ 不是内奸，则 $n$ 不可能是内奸。诸此。

具体的实现由递归完成，如下：

program Provo;

type
  TArray=array[1..30]of boolean;

var
  g,v:array[1..30,1..30]of boolean;
  d:TArray;
  n,m,i,j,a,b,c,cas:longint;

procedure search(p:longint);
  var
    i,j:integer;
    flag:boolean;
  begin
    if p>n
      then begin
        flag:=true;
        for i:=1 to n do
          for j:=1 to n do
            if v[i,j]
              then if (d[i] xor g[i,j]<> d[j])
                then flag:=false;
        if flag=false then exit;
        inc(cas);
        write('case ',cas,':');
        flag:=true;
        for i:=1 to n do
          if d[i]
            then begin
              write(' ',i);
              flag:=false;
            end;
        if flag then write(' None');
        writeln;
        exit;
      end;

    d[p]:=true;
    flag:=true;
    for i:=1 to p-1 do
      if v[i,p]
        then if not(d[i] xor g[i,p])
               then begin
                 flag:=false;break;
               end;
    if flag then search(p+1);
    d[p]:=false;
    flag:=true;
    for i:=1 to p-1 do
      if v[i,p]
        then if (d[i] xor g[i,p])
               then begin
                 flag:=false;break;
               end;
    if flag then search(p+1);
  end;

begin
  readln(n,m);
  fillchar(v,sizeof(v),false);
  for i:=1 to m do
  begin
    readln(a,b,c);
    v[a,b]:=true;
    g[a,b]:=(c=1);
  end;

  cas:=0;
  search(1);
  if cas=0 then writeln('No solution');

  close(input);close(output);
end.