#include <bits/stdc++.h>
#define REP(i,b,n) for(int i=(int)(b);i<(int)(n);++i)
#define rep(i,n) REP(i,0,n)
using namespace std;
struct G{
struct E{ int t, c; };
int n;
vector<vector<E>> g;
G(int n) : n(n), g(n){}
void add_undirected_edge(int s, int t, int c){
g[s].emplace_back(E{t, c});
g[t].emplace_back(E{s, c});
}
// undirected なのだけ. (そうでなくしたければ, 逆グラフを作る)
int dijk(int s, int t){
vector<priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>> pq(2);
vector<vector<int>> d(2, vector<int>(n, numeric_limits<int>::max() / 2));
pq[0].emplace(d[0][s] = 0, s);
pq[1].emplace(d[1][t] = 0, t);
vector<int> fin(n);
for(bool cont = true; cont and !pq[0].empty() and !pq[1].empty(); ){
for(int i = 0; i < 2; ++i){
if(pq[i].empty()) continue;
int u, c; tie(c, u) = pq[i].top(); pq[i].pop();
if(c > d[i][u]) continue;
if(++fin[u] == 2){
cont = false;
break;
}
for(auto &e : g[u]) if(d[i][e.t] > c + e.c)
pq[i].emplace(d[i][e.t] = c + e.c, e.t);
}
}
int res = numeric_limits<int>::max();
for(int u = 0; u < n; ++u) res = min(res, d[0][u] + d[1][u]);
return res;
}
};
bool solve(){
int n, m; cin >> n >> m;
G g(n);
rep(_, m){
int u, v, c; cin >> u >> v >> c;
g.add_undirected_edge(--u, --v, c);
}
cout << g.dijk(0, n-1) << endl;
return true;
}
signed main(){
cin.tie(nullptr);
ios_base::sync_with_stdio(false);
cout << std::fixed << std::setprecision(10);
solve();
return 0;
}
// vim:set foldmethod=marker commentstring=//%s:
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CiNkZWZpbmUgUkVQKGksYixuKSBmb3IoaW50IGk9KGludCkoYik7aTwoaW50KShuKTsrK2kpCiNkZWZpbmUgcmVwKGksbikgUkVQKGksMCxuKQp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKc3RydWN0IEd7CiAgICBzdHJ1Y3QgRXsgaW50IHQsIGM7IH07CiAgICBpbnQgbjsKICAgIHZlY3Rvcjx2ZWN0b3I8RT4+IGc7CiAgICBHKGludCBuKSA6IG4obiksIGcobil7fQogICAgdm9pZCBhZGRfdW5kaXJlY3RlZF9lZGdlKGludCBzLCBpbnQgdCwgaW50IGMpewogICAgICAgIGdbc10uZW1wbGFjZV9iYWNrKEV7dCwgY30pOwogICAgICAgIGdbdF0uZW1wbGFjZV9iYWNrKEV7cywgY30pOwogICAgfQogICAgLy8gdW5kaXJlY3RlZCDjgarjga7jgaDjgZEuICjjgZ3jgYbjgafjgarjgY/jgZfjgZ/jgZHjgozjgbAsIOmAhuOCsOODqeODleOCkuS9nOOCiykKICAgIGludCBkaWprKGludCBzLCBpbnQgdCl7CiAgICAgICAgdmVjdG9yPHByaW9yaXR5X3F1ZXVlPHBhaXI8aW50LCBpbnQ+LCB2ZWN0b3I8cGFpcjxpbnQsIGludD4+LCBncmVhdGVyPHBhaXI8aW50LCBpbnQ+Pj4+IHBxKDIpOwogICAgICAgIHZlY3Rvcjx2ZWN0b3I8aW50Pj4gZCgyLCB2ZWN0b3I8aW50PihuLCBudW1lcmljX2xpbWl0czxpbnQ+OjptYXgoKSAvIDIpKTsKICAgICAgICBwcVswXS5lbXBsYWNlKGRbMF1bc10gPSAwLCBzKTsKICAgICAgICBwcVsxXS5lbXBsYWNlKGRbMV1bdF0gPSAwLCB0KTsKICAgICAgICB2ZWN0b3I8aW50PiBmaW4obik7CiAgICAgICAgZm9yKGJvb2wgY29udCA9IHRydWU7IGNvbnQgYW5kICFwcVswXS5lbXB0eSgpIGFuZCAhcHFbMV0uZW1wdHkoKTsgKXsKICAgICAgICAgICAgZm9yKGludCBpID0gMDsgaSA8IDI7ICsraSl7CiAgICAgICAgICAgICAgICBpZihwcVtpXS5lbXB0eSgpKSBjb250aW51ZTsKICAgICAgICAgICAgICAgIGludCB1LCBjOyB0aWUoYywgdSkgPSBwcVtpXS50b3AoKTsgcHFbaV0ucG9wKCk7CiAgICAgICAgICAgICAgICBpZihjID4gZFtpXVt1XSkgY29udGludWU7CiAgICAgICAgICAgICAgICBpZigrK2Zpblt1XSA9PSAyKXsKICAgICAgICAgICAgICAgICAgICBjb250ID0gZmFsc2U7CiAgICAgICAgICAgICAgICAgICAgYnJlYWs7CiAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICBmb3IoYXV0byAmZSA6IGdbdV0pIGlmKGRbaV1bZS50XSA+IGMgKyBlLmMpCiAgICAgICAgICAgICAgICAgICAgcHFbaV0uZW1wbGFjZShkW2ldW2UudF0gPSBjICsgZS5jLCBlLnQpOwogICAgICAgICAgICB9CiAgICAgICAgfQogICAgICAgIGludCByZXMgPSBudW1lcmljX2xpbWl0czxpbnQ+OjptYXgoKTsKICAgICAgICBmb3IoaW50IHUgPSAwOyB1IDwgbjsgKyt1KSByZXMgPSBtaW4ocmVzLCBkWzBdW3VdICsgZFsxXVt1XSk7CiAgICAgICAgcmV0dXJuIHJlczsKICAgIH0KfTsKCmJvb2wgc29sdmUoKXsKICAgIGludCBuLCBtOyBjaW4gPj4gbiA+PiBtOwogICAgRyBnKG4pOwogICAgcmVwKF8sIG0pewogICAgICAgIGludCB1LCB2LCBjOyBjaW4gPj4gdSA+PiB2ID4+IGM7CiAgICAgICAgZy5hZGRfdW5kaXJlY3RlZF9lZGdlKC0tdSwgLS12LCBjKTsKICAgIH0KICAgIGNvdXQgPDwgZy5kaWprKDAsIG4tMSkgPDwgZW5kbDsKICAgIHJldHVybiB0cnVlOwp9CnNpZ25lZCBtYWluKCl7CiAgICBjaW4udGllKG51bGxwdHIpOwogICAgaW9zX2Jhc2U6OnN5bmNfd2l0aF9zdGRpbyhmYWxzZSk7CiAgICBjb3V0IDw8IHN0ZDo6Zml4ZWQgPDwgc3RkOjpzZXRwcmVjaXNpb24oMTApOwogICAgc29sdmUoKTsKICAgIHJldHVybiAwOwp9Ci8vIHZpbTpzZXQgZm9sZG1ldGhvZD1tYXJrZXIgY29tbWVudHN0cmluZz0vLyVzOg==