#include <cstdio>
#include <queue>
#include <vector>
using std::vector;
using std::priority_queue;

struct State {
    int len, to;
    State(int len, int to) : len(len), to(to) {}
    bool operator <(const State &rhs) const {
        if (len != rhs.len) {
            return len > rhs.len;
        }
        return to < rhs.to;
    }
};

const int maxN = 300;
int maxValue;

int N, M;
vector<vector<State>> graph;
priority_queue<State> pQueue;
int distTo[maxN];
bool used[maxN];

void dijkstra(int start) {
    memset(distTo, 63, sizeof(distTo));
    maxValue = distTo[0];
    distTo[start] = 0;
    int currVertex, to;
    pQueue.push(State(0, start));
    while (!pQueue.empty()) {
        currVertex = pQueue.top().to;
        pQueue.pop();
        if (!used[currVertex]) {
            used[currVertex] = true;
            for (auto &state : graph[currVertex]) {
                to = state.to;
                if (!used[to] && distTo[to] > distTo[currVertex] + state.len) {
                    distTo[to] = distTo[currVertex] + state.len;
                    pQueue.push(state);
                }
            }
        }
    }
}

int minCycle;
vector<vector<int>> cycles;
void DFS(int currVertex, int n, vector<int>& cycle) {
    int v;
    for (auto &state : graph[currVertex]) {
        v = state.to;
        if (v == 0 && n >= 2) {

        }
        if (!used[v]) {
            used[v] = true;
            DFS(v, n + 1);
            used[v] = false;
        }
    }
}
int main()
{
    scanf("%d %d", &N, &M);
    int from, to, len, start;
    graph.resize(N);
    for (int i = 0; i < M; i++)
    {
        scanf("%d %d %d", &from, &to, &len);
        graph[from - 1].push_back(State(len, to - 1));
        graph[to - 1].push_back(State(len, from - 1));
    }
    dijkstra(0);
    memset(used, 0, sizeof(used));
    minCycle = maxValue;
    used[0] = true;
    DFS(0, 0, 0);
    if (minCycle == maxValue) {
        printf("-1\n");
    }
    else {
        printf("%d\n", minCycle);
    }
    return 0;
}