#include <fstream>
#include <vector>
#include <queue>

using namespace std;

typedef pair<uint32_t, uint64_t> Edge;
bool operator < (const Edge &l, const Edge &r) {
    return l.second > r.second;
}

int main() {
    ifstream fin("input.txt");
    ofstream fout("output.txt");

    size_t vertexN, edgeN;
    fin >> vertexN >> edgeN;
    vector<uint64_t> dist(vertexN, UINT64_MAX);
    vector<vector<Edge>> edges(vertexN);

    for (uint32_t i = 0, a, b, weight; i < edgeN; ++i) {
        fin >> a >> b >> weight;
        --a; --b;
        edges[a].push_back(Edge(b, weight));
        edges[b].push_back(Edge(a, weight));
    }

    dist[0] = 0;
    priority_queue<Edge> minDistance;
    minDistance.push(make_pair(0, 0));

    while (!minDistance.empty()) {
        Edge current = minDistance.top();
        minDistance.pop();
        if (current.second <= dist[current.first]) {
            for (Edge next : edges[current.first]) {
                if (dist[next.first] > next.second + current.second) {
                    dist[next.first] = next.second + current.second;
                    minDistance.push(make_pair(next.first, dist[next.first]));
                }
            }
        }
    }

    fout << dist[vertexN - 1];

    return 0;
}