#include <bits/stdc++.h>
using namespace std;

#define int long long
#define mod 1000000007
#define pb push_back
#define S second
#define F first
#define INF 1e18
#define all(v) v.begin(), v.end()

#define deb(x) cerr << "\n" \
                    << #x << "=" << x << "\n";
#define deb2(x, y) cerr << "\n" \
                        << #x << "=" << x << "\n" \
                        << #y << "=" << y << "\n";
#define w(x) \
  int x;     \
  cin >> x;  \
  while (x--)

const int N = 1e5 + 2;
vector<pair<int,int>> v[N];
int n,m;
bool vis[N];
vector<pair<int,int>> dp(N,{-1,-1});

pair<int,int> dfs(int x) {
  if(x == n)
    return {0,0};

  if(dp[x].F != -1)
      return dp[x];

  if(vis[x]) return {INF,INF};

  int cost1 = INF,cost2 = INF;
  vis[x] = 1;
  for(pair<int,int> i: v[x]) {
    pair<int,int> temp = dfs(i.F);
    cost1 = min(cost1,temp.F + i.S);
    cost1 = min(cost1,temp.S + i.S / 2);

    cost2 = min(cost2, temp.S + i.S);
  }
  vis[x] = 0;

  // used = 1 or used = 0;
  return dp[x] = {cost1,cost2};
}
int32_t main() {

  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> m;
  for (int i = 0; i < m; i++) {
    int a, b, c;
    cin >> a >> b >> c;
    v[a].push_back({b,c});
  }
  cout << dfs(1).F;
  return 0;
}