#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define ff first
#define ss second
vector<vector<pair<ll,ll>>> adj;
vector<bool> vis;
ll dp[100005][2];
ll n,m;
ll dfs(ll node,bool flag){
if(node==n-1) return 0;
if(dp[node][flag]!=-1) return dp[node][flag];
vis[node]=true;
ll k=1e18;
for(auto e:adj[node]){
int child=e.first;
ll weight=e.ss;
if(!vis[child]){
if(flag){
k=min(k,weight/2+dfs(child,false));
}
k=min(k,weight+dfs(child,flag));
}
}
vis[node]=false;
return dp[node][flag]=k;
}
int main(){
cin>>n>>m;
adj.resize(n);
vis.resize(n);
memset(dp,-1,sizeof dp);
for(ll i=0;i<m;i++){
ll u,v,w; cin>>u>>v>>w;
adj[u-1].pb({v-1,w});
}
cout<<dfs(0,true);
return 0;
}
I2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKIAogCiNkZWZpbmUgbGwgbG9uZyBsb25nCiNkZWZpbmUgcGIgcHVzaF9iYWNrCiNkZWZpbmUgZmYgZmlyc3QKI2RlZmluZSBzcyBzZWNvbmQKIAp2ZWN0b3I8dmVjdG9yPHBhaXI8bGwsbGw+Pj4gYWRqOwp2ZWN0b3I8Ym9vbD4gdmlzOwpsbCBkcFsxMDAwMDVdWzJdOwpsbCBuLG07CiAKbGwgZGZzKGxsIG5vZGUsYm9vbCBmbGFnKXsKICAgIAogICAgaWYobm9kZT09bi0xKSByZXR1cm4gMDsKICAgICAKICAgIGlmKGRwW25vZGVdW2ZsYWddIT0tMSkgcmV0dXJuIGRwW25vZGVdW2ZsYWddOwogICAgCiAgICB2aXNbbm9kZV09dHJ1ZTsKICAgIGxsIGs9MWUxODsKIAogICAgZm9yKGF1dG8gZTphZGpbbm9kZV0pewogICAgICAgIAogICAgICAgIGludCBjaGlsZD1lLmZpcnN0OwogICAgICAgIGxsIHdlaWdodD1lLnNzOwogICAgICAgIAogICAgICAgIGlmKCF2aXNbY2hpbGRdKXsKICAgICAgICAgICAgaWYoZmxhZyl7CiAgICAgICAgICAgICAgICBrPW1pbihrLHdlaWdodC8yK2RmcyhjaGlsZCxmYWxzZSkpOwogICAgICAgICAgICAgICAgCiAgICAgICAgICAgIH0KICAgICAgICAgICAgaz1taW4oayx3ZWlnaHQrZGZzKGNoaWxkLGZsYWcpKTsKICAgICAgICAgICAgCiAgICAgICAgfQogICAgICAgIAogICAgfQogICAgCiAgICB2aXNbbm9kZV09ZmFsc2U7CiAgICAKICAgIHJldHVybiBkcFtub2RlXVtmbGFnXT1rOwogICAgCiAgICAKfQogCiAKaW50IG1haW4oKXsKICAgIAogICAgY2luPj5uPj5tOwogICAgCiAgICBhZGoucmVzaXplKG4pOwogICAgdmlzLnJlc2l6ZShuKTsKICAgIAogICAgbWVtc2V0KGRwLC0xLHNpemVvZiBkcCk7CiAKICAgCiAgICBmb3IobGwgaT0wO2k8bTtpKyspewogICAgICAgIGxsIHUsdix3OyBjaW4+PnU+PnY+Pnc7CiAgICAgICAgYWRqW3UtMV0ucGIoe3YtMSx3fSk7CiAgICB9CiAgIAogICAgY291dDw8ZGZzKDAsdHJ1ZSk7CiAgICAKICAgIHJldHVybiAwOwogICAgCn0=