#include <bits/stdc++.h>
#define int long long

using namespace std;

vector <pair<int, int> g[300];

int dist[300];
int p[300];

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int x, y, v;
        cin >> x >> y >> v;
        g[x - 1].push_back({y - 1, v});
        g[y - 1].push_back({x - 1, v});
    }
    set <pair <int, int>> s;
    dist[0] = 0;
    p[0] = -1;
    s.insert({0, 0});
    while (s.size() > 0) {
        int v = s.begin() -> second;
        s.erase(s.begin());
        for (auto u : g[v]) {
            if (dist[u.first] > dist[v] + u.second) {
                s.erase({u.first, dist[u.first]});
                dist[u.first] = dist[v] + u.second;
                p[u.first] = v;
                s.insert({u.first, dist[u.first]});
            }
        }
    }
    int ans = dist[n - 1];
    int k = n - 1;
    vector <int> put = {k};
    while (p[k] != -1) {
        put.push_back(p[k]);
        k = p[k];
    }
    int anr = 1e18;
    for (int i = 0; i < put.size() - 1; i++) {
        for (int j = 0; j < g[put[i]].size(); j++) {
            if (g[put[i]][j].first == put[i + 1]) {
                g[put[i]][j].second *= 2;
            }
        }
        for (int j = 0; j < g[put[i + 1]].size(); j++) {
            if (g[put[i + 1]][j].first == put[i]) {
                g[put[i + 1]][j].second *= 2;
            }
        }

    }
    return 0;
}