#include <bits/stdc++.h>
#include <atcoder/all>
#include <ranges>
using namespace std;
using namespace atcoder;
//loop
#define REP(i, n) for (ll i = 0; i < (ll)(n); i++)
//vector
#define ALL(A) A.begin(), A.end()
#define RV(A) reverse(ALL(A))
#define RALL(A) A.rbegin(), A.rend()
#define SORT(A) sort(ALL(A))
#define RSORT(A) sort(RALL(A))
//input
template<class T> inline void input(T& a) { cin >> a; }
template<class T> inline void input_li(T& a) {for(auto &ob:a) cin >> ob;}
template<class... T> inline void input(T&... a) { ((cin >> a), ...); }
//output
#define Yes(bo)  cout << ((bo) ? "Yes":"No") << endl
#define YES(bo)  cout << ((bo) ? "YES":"NO") << endl
#define yes(bo)  cout << ((bo) ? "yes":"no") << endl
#define Taka(bo) cout << ((bo) ? "Takahashi":"Aoki") << endl
//other
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define sz size
#define is insert
#define ps push
#define tp top
#define ft front
#define pp pop
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0;}
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0;}
//const
#define I_MAX   2147483647
#define I_MIN   -2147483647
#define UI_MAX  4294967295
#define LL_MAX  9223372036854775807
#define LL_MIN  -9223372036854775808
#define ULL_MAX 18446744073709551615
//type
using ll      = long long;
using ull     = unsigned long long;
using ld      = long double;
using Pair    = pair<ll,ll>;
using vll     = vector<ll>;
using mint    = modint998244353;
using mint1   = modint1000000007;
const ll Inf = 1LL << 60;
//debug
#ifdef _DEBUG
    #define debug(x)    cerr << "dbg_var : " << #x << ": " << x << endl
    #define debug2(x,y) cerr << "dbg_var : " << #x << ": " << x  << " "<< #y << ": " << y << endl
    #define debug3(x,y,z) cerr << "dbg_var : " << #x << ": " << x << " "<< #y << ": " << y << " " <<  #z << ": " << z <<endl
    #define debug_v(x)  cerr << "dbg_vect: " << #x << ": "; for(auto v:x) cerr << v << " "; cerr << endl
    #define debug_s(x)  cerr << "dbg_set : " << #x << ": {"; for(auto v:x) cerr << v << ","; cerr << "}" << endl
    #define debug_p(x)  cerr << "dbg_pair: " << #x << "Fir: " << x.first << " Sec: " << x.second << endl
    #define debug_m(x)  cerr << "dbg_map : " << #x << ": "; for(auto Ite1:x)cerr << "key: " << Ite1.first << " : " << Ite1.second << ", "; cerr<< endl
    #define debug_l()   cerr << "======================================" << endl
#else
    #define debug(x)
    #define debug2(x,y)
    #define debug3(x,y,z)
    #define debug_v(x)
    #define debug_s(x)
    #define debug_p(x)
    #define debug_m(x)
    #define debug_l()
#endif
ll getSum(vector<ll> b) {ll res=0;for(auto v:b){res+=v;}return res;}
ll GCD(ll a, ll b) {if (b == 0) return a;else return GCD(b, a % b);}
ll LCM(ll a, ll b) {ll d=GCD(a,b);return (a/d)*(b/d)*d;}
/*zahyou to ka*/
bool poich(ll P,ll Q){return(0<=P&&P<Q);}
bool poich2(ll i,ll j,ll H,ll W){return(poich(j,W)&&poich(i,H));}
vector<Pair> dxy{{1,0},{-1,0},{0,1},{0,-1}};
//https://algo-logic.info/calc-pow/
ll dpow(ll x, ll n,ll mod) {
    ll ret = 1;
    while (n > 0) {
        if (n & 1) ret = ret * x % mod;
        x = x * x % mod;
        n >>= 1;
    }
    return ret;
}
ll chd21(ll N,ll i,ll j){
    return N*i+j;
}
Pair chd12(ll N,ll X){
    return {X/N,X%N};
}
//input
template <class T>
void input_v(vector<T> &vec){
    for(auto &v:vec)cin >> v;
}
vector<ll> MakePrime(long long MAX_N){
    vector<long long> Isprime,Prime;
    Isprime.resize(MAX_N+2,true);
    Isprime[0]=false;
    Isprime[1]=false;
    for(long long i=2;i*i<=MAX_N;i++){
        if(Isprime[i]){
            for(long long j=i*i;j<=MAX_N;j+=i)Isprime[j]=false;
        }
    }
    for(long long i=0;i<MAX_N;i++)if(Isprime[i])Prime.push_back(i);
    return Prime;
}
template<class T>
struct comb{
    public:
    comb():comb(10000000){}
    comb(ll N):A(N,1),B(N,1){
        for(ll i=0;i<N;i++){
            A[i+1]=A[i]*(i+1);
            B[i+1]=1/A[i+1];
        }
    }
    T nCk1(ll n,ll k){
        
        if(n<0||k<0||n-k<0)return (T)0;
        return A[n]*B[k]*B[n-k];
    }
    T nPk1(ll n,ll k){
        
        if(n<0||k<0||n-k<0)return (T)0;
        return A[n]*B[k];
    }
    T nCk2(ll n,ll k){
        T res=1;
        for(ll i=k+1;i<=n;i++){
            res*=i;
        }
        for(ll i=0;i<=n-k;i++){
            res/=i;
        }
        return res;
    }
    vector<T> A;
    vector<T> B;
};
vector<array<ll,2>> totu_cover(vector<array<ll,2>> points){
    vector<array<ll,2>> p=points; 
    sort(p.begin(),p.end());
    ll N=p.size();
    auto func=[&](bool bo){
        stack<array<ll,2>> st;
        queue<array<ll,2>> que;
        ll k=2*bo-1;
        for(ll i=N-1;i>=0;i--){
            que.push(p[i]);
        }
        while(!que.empty()){
            auto v=que.front();
            if(st.size()<2){
                st.push(v);
                que.pop();
            }else{
                auto o=st.top();st.pop();
                auto t=st.top();
                auto[a,b]=t;
                auto[c,d]=o;
                auto[e,f]=v;
                if((f-b)*(a-c)*k>(d-b)*(a-e)*k){
                    continue;
                }else{
                    st.push(o);
                    st.push(v);
                    que.pop();
                }
            }
        }
        vector<array<ll,2>> res;
        while(!st.empty()){
            res.push_back(st.top());
            st.pop();
        }
        return res;
    };
    auto v=func(1);
    auto u=func(0);
    ll vn=v.size(),un=u.size();
    vector<array<ll,2>> ans;
    set<array<ll,2>> cot;
    for(ll i=vn-1;i>=0;i--){
        ans.push_back(v[i]);
        cot.insert(v[i]);
    }
    for(ll i=0;i<un;i++){
        if(!cot.count(u[i])){
            ans.push_back(u[i]);
        }
        cot.insert(u[i]);
    }
    return ans;
}

struct Edge{
    Edge(ll t) : to(t){}
    ll to;
};
struct WeightEdge{
    public:
    WeightEdge(ll t,ll c) : to(t),cost(c) {}
    ll to,cost;
    bool operator<(const WeightEdge &other)const{
        return cost<other.cost;
    }
    bool operator>(const WeightEdge &other)const{
        return cost>other.cost;
    }
    bool operator<=(const WeightEdge &other)const{
        return cost<=other.cost;
    }
    bool operator>=(const WeightEdge &other)const{
        return cost>=other.cost;
    }
};
//Graph
struct Graph{
    public:
    Graph(int n,ll e=0) : graph(n),N(n){
    }
    void addedge(ll u,ll v){
        graph[u].push_back(Edge(v));
    }
    int size(){
        return N;
    }
    int jisuu(int p){
        return graph[p].size();
    }
    ll N;
    vector<vector<Edge>> graph;
};
struct WeightGraph{
    public:
    WeightGraph(int n,ll e=0) : graph(n),N(n){
    }
    void addedge(ll u,ll v,ll c){
        graph[u].push_back(WeightEdge(v,c));
    }
    int size(){
        return N;
    }
    int jisuu(int p){
        return graph[p].size();
    }
    ll N;
    vector<vector<WeightEdge>> graph;
};
vector<ll> normal_bfs(Graph graph,ll s=0){
    vector<ll> dist(graph.size(),Inf);
    dist[s]=0;
    queue<ll> que;
    que.push(s);
    while(!que.empty()){
        ll a=que.front();que.pop();
        for(auto v:graph.graph[a]){
            if(dist[v.to]==Inf){
                dist[v.to]=dist[a]+1;
                que.push(v.to);
            }
        }
    }
    return dist;
}
void solve(){
    ll N,M;cin >> N >> M;
    Graph graph(2*N);
    for(ll i=0;i<M;i++){
        ll a,b,c;cin >> a >> b >> c;
        a--,b--;
        if(c==1){
            graph.addedge(a,b);
            graph.addedge(b,a);
            graph.addedge(a+N,b+N);
            graph.addedge(b+N,a+N);
        }else{
            graph.addedge(a,b+N);
            graph.addedge(b,a+N);
        }
    }
    auto dist=normal_bfs(graph,0);
    if(dist[2*N-1]!=Inf){
        cout << "Different" << endl;
        cout << dist[2*N-1] << endl;
    }else
    if(dist[N-1]!=Inf){
        cout << "Same" << endl;
        cout << dist[N-1] << endl;
    }else{
        cout << "Unknown" << endl;
    }
}
int main(){
    ll T=1;cin >> T;
    while(T--){
        solve();
    }
    return 0;
}