#include <bits/stdc++.h>
#define int long long
using namespace std;
int n,m,d[300005];
vector <int> q[3000006];
vector <pair<int,int>> ve[300005];
void DIAL(int be)
{
    for (int i=1;i<=n;i++) d[i]=1e9;
    d[be]=0,q[0].push_back(be);
    for (int dis=0;dis<=10*(n-1);dis++)
    {
        while (q[dis].size())
        {
            int u=q[dis].back();
            q[dis].pop_back();
            if (d[u]<dis) continue;
            for (pair <int,int> p : ve[u])
            {
                int v=p.first,w=p.second;
                if (d[v]>d[u]+w) d[v]=d[u]+w,q[d[v]].push_back(v);
            }
        }
    }
    cout<<d[n];
}
signed main()
{
    ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for (int i=1;i<=m;i++)
    {
        int u,v,w;
        cin>>u>>v>>w;
        ve[u].push_back({v,w}),ve[v].push_back({u,w});
    }
    DIAL(1);
    return 0;
}