#include <bits/stdc++.h>
// what the fuck
template<typename T, int N>
struct NDVector { using type = std::vector<typename NDVector<T, N - 1>::type>; };
template<typename T>
struct NDVector<T, 1> { using type = std::vector<T>; };
// A tensor is essentially a vector of tensors. (or multidimensional array)
template<typename T, int N>
using Tensor = typename NDVector<T, N>::type;
/**
* Create a multidimensional vector with the given dimension sizes.
*
* In particular, create_vector(N) = create_tensor(N), create_matrix(N, M) = create_tensor(N, M).
* If you have some weird multidimensional DP, you can create the DP table by doing:
* dp = create_tensor(5, 5, 5, 5, 5);
*
* Be careful, for a large number of dimensions, this uses a lot of memory and is very cache unfriendly.
*/
template<typename T>
std::vector<T> create_tensor(int N) {
return std::vector<T>(N);
}
template <typename T, typename... ArgTypes>
Tensor<T, sizeof...(ArgTypes) + 1> create_tensor(int N, ArgTypes... args) {
auto under = create_tensor<T>(args...);
return std::vector(N, under);
}
/**
* Create a matrix of the given dimensions.
*/
template<typename T>
Tensor<T, 2> create_matrix(int N, int M) {
return create_tensor<T>(N, M);
}
/**
* Frequently used definitions, like Vector, Matrices, pairs of ints, pairs, triples, etc.
*/
template<typename T>
using Vector = Tensor<T, 1>; // I could use std::vector<T>, but this is just too cool.
template<typename T>
using Matrix = Tensor<T, 2>;
template<typename T1, typename T2>
using Pair = std::pair<T1, T2>;
using PairII = Pair<int, int>;
using PairLL = Pair<long long, long long>;
template<typename T1, typename T2, typename T3>
using Triple = std::tuple<T1, T2, T3>;
/**
* Read a vector from input. Set start to 1 if you want it to be 1-indexed.
*/
template<typename T>
Vector<T> read_vector(int N, int start = 0) {
Vector<T> v(start + N);
for (int i = start; i < (int)v.size(); i++) {
std::cin >> v[i];
}
return v;
}
/**
* Read a matrix from input. Set start_l to make lines 1-indexed. Same thing for start_c.
*/
template<typename T>
Matrix<T> read_matrix(int N, int M, int start_l = 0, int start_c = 0) {
Matrix<T> matr = create_matrix<T>(N + start_l, M + start_c);
for (int l = start_l; l < N + start_l; l++)
for (int c = start_c; c < M + start_c; c++)
std::cin >> matr[l][c];
return matr;
}
/**
* Print a tensor to the output stream. Prints all indices between i and j, and the elements
* are separated by the given separator.
*
* To generalize, for each dimension, you give the bounds that you want to print and the separator
* between each order. To print a matrix, you would do:
*
* print_tensor(matr, std::cout, 0, N - 1, "\n", 0, M - 1, " ");
*/
template<typename T>
void print_tensor(Tensor<T, 1>& tens, std::ostream&fout, int i, int j, const char* sep) {
for (int t = std::max(i, 0); t <= j && t < (int)tens.size(); t++) {
fout << tens[t];
if (t + 1 <= j)
fout << sep;
}
}
template<typename T, typename... Sizes>
void print_tensor(
Tensor<T, sizeof...(Sizes) / 3 + 1>& tens,
std::ostream& fout,
int i, int j, const char* sep, Sizes... sizes) {
for (int t = std::max(i, 0); t <= j && t < (int)tens.size(); t++) {
print_tensor<T>(tens[t], fout, sizes...);
if (t + 1 <= j)
fout << sep;
}
}
/**
* Print a vector to the given output stream with given bounds and separator.
*/
template<typename T>
void print_vector(std::vector<T>& v, std::ostream& fout, int i = 0, int j = (1 << 30), const char* sep = " ") {
print_tensor<T>(v, fout, i, j, sep);
}
/**
* Read a vector of pairs. Set start to 1 if you want this to be 1-indexed.
*/
template<typename T1, typename T2>
Vector<Pair<T1, T2>> read_pairvec(int N, int start = 0) {
Vector<Pair<T1, T2>> input = Vector<Pair<T1, T2>>(start + N);
for (int i = start; i < start + N; i++)
std::cin >> input[i].first >> input[i].second;
return input;
}
/**
* Read a vector of triples. Set start to 1 if you want this to be 1-indexed.
*
* If you need higher order tuples, like quadruples, you're better off using a matrix instead.
*/
template<typename T1, typename T2, typename T3>
Vector<Triple<T1, T2, T3>> read_triplevec(int N, int start = 0) {
Vector<Triple<T1, T2, T3>> input = Vector<Triple<T1, T2, T3>>(start + N);
for (int i = start; i < N + start; i++) {
T1 a;
T2 b;
T3 c;
std::cin >> a >> b >> c;
input[i] = {a, b, c};
}
return input;
}
/**
* Removes duplicates from vector. Assumes it is sorted.
*/
template<typename T>
void deduplicate(Vector<T>& v) {
v.resize(std::unique(v.begin(), v.end()) - v.begin());
}
/**
* Solve a testcase of the problem. You will code your solution here instead of main.
*/
void solve_test();
/**
* Call this function if you have a problem with multiple testcases.
*/
void multitest_problem() {
int T;
std::cin >> T;
while (T--) solve_test();
}
int main() {
std::cin.tie(NULL);
std::iostream::sync_with_stdio(false);
// Choose one of the following functions, depending on the problem type.
solve_test();
//multitest_problem();
return 0;
}
void solve_test() {
int N, M;
std::cin >> N >> M;
auto edges = read_triplevec<int, int, int>(M);
Vector<Vector<PairII>> graph(1 + N);
for (auto [a, b, c] : edges)
graph[a].push_back({b, c});
auto vis = create_matrix<bool>(1 + N, 1 << 10);
vis[1][0] = true;
std::queue<PairII> q;
q.push({1, 0});
int res = 1 << 10;
while (!q.empty()) {
auto [n, c] = q.front();
q.pop();
if (n == N)
res = std::min(res, c);
for (auto [to, w] : graph[n]) {
if (!vis[to][c ^ w]) {
vis[to][c ^ w] = true;
q.push({to, c ^ w});
}
}
}
if (res == (1 << 10))
res = -1;
std::cout << res;
}