#include <iostream>
#include <queue>
#include <vector>
using namespace std;

struct node
{
    int idx;
    long long cost;
    int pop;
    node(){}
    node(int _idx, long long _cost, int _pop)
    {
        idx=_idx;
        cost=_cost;
        pop=_pop;
    }
    bool operator <(const node &tmp)const
    {
        return cost>tmp.cost;
    }
};
vector<pair<int,long long>>par[100005];
long long dis[100005][2];

int main()
{
    ios_base::sync_with_stdio(false);
    long long a,b,x,y,z;
    cin>>a>>b;
    int i, j;

    for( i=0;i<b;i++)
    {
        cin>>x>>y>>z;
        par[x].push_back({y,z});
    }
    priority_queue<node>Q;
    Q.push(node(1,0,0));
    for( i=0;i<=a;i++)
    {
        for( j=0;j<2;j++)
        {
            dis[i][j]=1e18;
        }
    }
    long long sosed, r;
    dis[1][0]=0;
    dis[1][1] = 0;
    while(!Q.empty())
    {
        node teme=Q.top();
        Q.pop();

        if(teme.cost > dis[teme.idx][teme.pop]) continue;
        for( i=0;i<par[teme.idx].size();i++)
        {
             sosed=par[teme.idx][i].first;
             r = par[teme.idx][i].second;
            if(teme.pop==0)
            {
                if(r + teme.cost<dis[sosed][teme.pop])
                {
                    dis[sosed][teme.pop]=r+teme.cost;
                    Q.push(node(sosed,dis[sosed][teme.pop],teme.pop));
                }
                if((r/2) + teme.cost<dis[sosed][1])
                {
                    dis[sosed][1]=r/2 + teme.cost;
                    Q.push(node(sosed,dis[sosed][1],1));
                }
            }
            else if(teme.pop==1)
            {
                if(r+teme.cost<dis[sosed][teme.pop])
                {
                    dis[sosed][teme.pop]=r+teme.cost;
                    Q.push(node(sosed,dis[sosed][teme.pop],teme.pop));
                }
            }
        }
    }
    cout << min(dis[a][0], dis[a][1]) << endl;
    return 0;
}