// prctice3.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <bits/stdc++.h>
#define int long long
#define ll long long
#define INF 0x3f3f3f3f3f3f3f
using namespace std;
const int N = 1e6 + 5;
struct edge {
    int u, v, w;
};
struct node {
    int id;
    int dis;
    node(int a, int b) { id = a, dis = b; }
    bool operator<(const node& u)const { return dis > u.dis; }
};
vector<int>a[N];
vector<edge>e(2*N);
bool vis[N];
int d[N];
int n, m;
void dij(int s) {
    for (int i = 0; i <= n; i++) {
        d[i] = INF;
        vis[i] = 0;
    }
    d[s] = 0;
    priority_queue<node>q;
    q.push(node(s, d[s]));
    while (!q.empty()) {
        node u = q.top();
        q.pop();
        if (vis[u.id])continue;
        vis[u.id] = 1;
        for (int i = 0; i < a[u.id].size(); i++) {
            edge y = e[a[u.id][i]];
            int v = y.v;
            if (vis[v])continue;
            if (d[v] > u.dis + y.w) {
                d[v] = u.dis + y.w;
                q.push(node(y.v, d[v]));
            }
        }
    }
}

void solve() {
   
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        e[i] = { u,v,w };
        e[i + m] = { u,v,w };
        a[u].push_back(i);
        a[v].push_back (i + m);
    }
    dij(1);
    cout << d[n] << endl;
}

signed main() {
    ios::sync_with_stdio(0);
    cout.tie(0), cout.tie(0);
    solve();
}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件