#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<map>
#include<cmath>
#include<iomanip>
#include<set>
using namespace std;
typedef long long ll;
#define rep(i, n) for (int i = 0; i < n; ++i)
#define rrep(i, st, n) for (int i = st; i < n; ++i)
using pii = pair<int, int>;
int main() {
const int inf = 300 * 100000;
int n, m; cin >> n >> m;
int dp[n + 1][n + 1]; rep(i, n + 1) rep(j, n + 1) dp[i][j] = inf;
rep(i, m) {int u, v, l; cin >> u >> v >> l; dp[u][v] = l; dp[v][u] = l;}
vector<int> v;
v.resize(0);
rrep(i, 1, n + 1) if (dp[i][1] != inf) v.push_back(i);
int dp2[n + 1][n + 1]; rep(i, n + 1) rep(j, n + 1) dp2[i][j] = dp[i][j];
rrep(i, 1, n + 1) {dp[1][i] = inf; dp[i][1] = inf;}
//rrep(i, 1, n + 1) {rrep(j, 1, n + 1) cout << dp[i][j] << " "; cout << endl;}
rrep(k, 1, n + 1) rrep(i, 1, n + 1) rrep(j, 1, n + 1) dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]);
//rrep(i, 1, n + 1) {rrep(j, 1, n + 1) cout << dp[i][j] << " "; cout << endl;}
int ans = inf;
rep(i, v.size()) rrep(j, i + 1, v.size()) ans = min(ans, dp2[1][v[i]] + dp[v[i]][v[j]] + dp2[v[j]][1]);
if (ans != inf) cout << ans << endl;
else cout << -1 << endl;
}
I2luY2x1ZGU8aW9zdHJlYW0+CiNpbmNsdWRlPHZlY3Rvcj4KI2luY2x1ZGU8YWxnb3JpdGhtPgojaW5jbHVkZTxxdWV1ZT4KI2luY2x1ZGU8bWFwPgojaW5jbHVkZTxjbWF0aD4KI2luY2x1ZGU8aW9tYW5pcD4KI2luY2x1ZGU8c2V0Pgp1c2luZyBuYW1lc3BhY2Ugc3RkOwp0eXBlZGVmIGxvbmcgbG9uZyBsbDsKI2RlZmluZSByZXAoaSwgbikgZm9yIChpbnQgaSA9IDA7IGkgPCBuOyArK2kpCiNkZWZpbmUgcnJlcChpLCBzdCwgbikgZm9yIChpbnQgaSA9IHN0OyBpIDwgbjsgKytpKQp1c2luZyBwaWkgPSBwYWlyPGludCwgaW50PjsKCmludCBtYWluKCkgewogICAgY29uc3QgaW50IGluZiA9IDMwMCAqIDEwMDAwMDsKICAgIGludCBuLCBtOyBjaW4gPj4gbiA+PiBtOwogICAgaW50IGRwW24gKyAxXVtuICsgMV07IHJlcChpLCBuICsgMSkgcmVwKGosIG4gKyAxKSBkcFtpXVtqXSA9IGluZjsKICAgIHJlcChpLCBtKSB7aW50IHUsIHYsIGw7IGNpbiA+PiB1ID4+IHYgPj4gbDsgZHBbdV1bdl0gPSBsOyBkcFt2XVt1XSA9IGw7fQogICAgdmVjdG9yPGludD4gdjsKICAgIHYucmVzaXplKDApOwogICAgcnJlcChpLCAxLCBuICsgMSkgaWYgKGRwW2ldWzFdICE9IGluZikgdi5wdXNoX2JhY2soaSk7CiAgICBpbnQgZHAyW24gKyAxXVtuICsgMV07IHJlcChpLCBuICsgMSkgcmVwKGosIG4gKyAxKSBkcDJbaV1bal0gPSBkcFtpXVtqXTsKICAgIHJyZXAoaSwgMSwgbiArIDEpIHtkcFsxXVtpXSA9IGluZjsgZHBbaV1bMV0gPSBpbmY7fQogICAgLy9ycmVwKGksIDEsIG4gKyAxKSB7cnJlcChqLCAxLCBuICsgMSkgY291dCA8PCBkcFtpXVtqXSA8PCAiICI7IGNvdXQgPDwgZW5kbDt9CiAgICBycmVwKGssIDEsIG4gKyAxKSBycmVwKGksIDEsIG4gKyAxKSBycmVwKGosIDEsIG4gKyAxKSBkcFtpXVtqXSA9IG1pbihkcFtpXVtqXSwgZHBbaV1ba10gKyBkcFtrXVtqXSk7CiAgICAvL3JyZXAoaSwgMSwgbiArIDEpIHtycmVwKGosIDEsIG4gKyAxKSBjb3V0IDw8IGRwW2ldW2pdIDw8ICIgIjsgY291dCA8PCBlbmRsO30KICAgIGludCBhbnMgPSBpbmY7CiAgICByZXAoaSwgdi5zaXplKCkpIHJyZXAoaiwgaSArIDEsIHYuc2l6ZSgpKSBhbnMgPSBtaW4oYW5zLCBkcDJbMV1bdltpXV0gKyBkcFt2W2ldXVt2W2pdXSArIGRwMlt2W2pdXVsxXSk7CiAgICBpZiAoYW5zICE9IGluZikgY291dCA8PCBhbnMgPDwgZW5kbDsKICAgIGVsc2UgY291dCA8PCAtMSA8PCBlbmRsOwp9Cg==