#include <iostream>
#include <sstream>
#include <iomanip>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <algorithm>
#include <numeric>
#include <iterator>
#include <functional>
#include <complex>
#include <queue>
#include <stack>
#include <cmath>
#include <cassert>
#include <tuple>
using namespace std;
typedef long long LL;
typedef complex<double> CMP;
class LongLongTripDiv1 { public:
string isAble(int N, vector <int> A, vector <int> B, vector <int> D, long long T)
{
return solve(N, A, B, D, T) ? "Possible" : "Impossible";
}
bool solve(int N, const vector <int>& A, const vector <int>& B, const vector <int>& D, long long T)
{
vector<vector<pair<int,int>>> edges(N);
for(int i=0; i<A.size(); ++i) {
edges[A[i]].emplace_back(B[i], D[i]);
edges[B[i]].emplace_back(A[i], D[i]);
}
if(!solve_mod(99961, N, edges, T))
return false;
if(!solve_mod(99971, N, edges, T))
return false;
if(!solve_mod(99989, N, edges, T))
return false;
if(!solve_mod(99991, N, edges, T))
return false;
for(int mod=2; mod<=1000; ++mod)
if(!solve_mod(mod, N, edges, T))
return false;
return true;
}
bool solve_mod(int mod, int N, const vector<vector<pair<int,int>>>& E, long long T)
{
vector<bool> V(mod*N); V[0*mod+0] = true;
queue<int> Q; Q.push(0*mod+0);
while(!Q.empty())
{
int v = Q.front() / mod;
int m = Q.front() % mod;
Q.pop();
for(auto ud : E[v]) {
int u = ud.first;
int d = ud.second;
int m2 = (m+d)%mod;
if(!V[u*mod+m2]) {
V[u*mod+m2] = true;
Q.push(u*mod+m2);
}
}
}
return V[(N-1)*mod+int(T%mod)];
}
};
// BEGIN CUT HERE
#include <ctime>
double start_time; string timer()
{ ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
{ os << "{ ";
for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
void verify_case(const string& Expected, const string& Received) {
bool ok = (Expected == Received);
if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl;
cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
#define END verify_case(_, LongLongTripDiv1().isAble(N, A, B, D, T));}
int main(){
CASE(6)
int N = 50;
int A_[] = {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1};
vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_));
int B_[] = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,2};
vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_));
int D_[] = {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1};
vector <int> D(D_, D_+sizeof(D_)/sizeof(*D_));
long long T = 1000000000000000000LL;
string _ = "Possible";
END
CASE(0)
int N = 3;
int A_[] = {0,0,1};
vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_));
int B_[] = {2,1,2};
vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_));
int D_[] = {7,6,5};
vector <int> D(D_, D_+sizeof(D_)/sizeof(*D_));
long long T = 11LL;
string _ = "Possible";
END
CASE(1)
int N = 3;
int A_[] = {0,0,1};
vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_));
int B_[] = {2,1,2};
vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_));
int D_[] = {7,6,5};
vector <int> D(D_, D_+sizeof(D_)/sizeof(*D_));
long long T = 25LL;
string _ = "Possible";
END
CASE(2)
int N = 2;
int A_[] = {0};
vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_));
int B_[] = {1};
vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_));
int D_[] = {1};
vector <int> D(D_, D_+sizeof(D_)/sizeof(*D_));
long long T = 9LL;
string _ = "Possible";
END
CASE(3)
int N = 2;
int A_[] = {1};
vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_));
int B_[] = {0};
vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_));
int D_[] = {1};
vector <int> D(D_, D_+sizeof(D_)/sizeof(*D_));
long long T = 1000000000000000000LL;
string _ = "Impossible";
END
CASE(4)
int N = 4;
int A_[] = {0,0,1};
vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_));
int B_[] = {2,1,2};
vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_));
int D_[] = {10,10,10};
vector <int> D(D_, D_+sizeof(D_)/sizeof(*D_));
long long T = 1000LL;
string _ = "Impossible";
END
CASE(5)
int N = 9;
int A_[] = {4,8,5,8,3,6,2,6,7,6,6};
vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_));
int B_[] = {2,7,1,5,1,3,1,1,5,4,2};
vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_));
int D_[] = {6580,8822,1968,673,1394,9337,5486,1746,5229,4092,195};
vector <int> D(D_, D_+sizeof(D_)/sizeof(*D_));
long long T = 937186357646035002LL;
string _ = "Impossible";
END
}
// END CUT HERE