#include <stdio.h>
#include <vector>
#define ll long long
const long long INF = 10000000000000000L;
using namespace std;
int main(int argc, char* argv[])
{
int cities, flights;
scanf("%d %d", &cities, &flights);
vector<vector<pair<int, int> > > cityList(cities);
for (int i = 0; i < flights; i++){
int from, to, price;
scanf("%d %d %d", &from, &to, &price);
if (from != cities){
from--;
to--;
cityList[from].push_back(make_pair(to, price));
}
}
vector<int> z;
vector<pair<ll, ll> > price(cities, make_pair(INF, INF));
price[0] = make_pair(INF, 0);
z.push_back(0);
for (unsigned int i = 0; i < z.size(); i++) {
for (unsigned int j = 0; j < cityList[z[i]].size(); j++) {
int u = cityList[z[i]][j].first;
bool b = false;
if (price[u].first > (price[z[i]].second + cityList[z[i]][j].second)){
if (price[z[i]].second + cityList[z[i]][j].second < price[cities - 1].first && price[z[i]].second + cityList[z[i]][j].second < price[cities - 1].second){
price[u].first = price[z[i]].second + cityList[z[i]][j].second;
b = true;
}
}
if (price[u].second > (price[z[i]].first)){
if (price[z[i]].first + cityList[z[i]][j].second < price[cities - 1].first && price[z[i]].first + cityList[z[i]][j].second < price[cities - 1].second){
price[u].second = price[z[i]].first;
b = true;
}
if (b)
z.push_back(u);
}
}
if (price[cities - 1].first != INF){
if (price[cities - 1].second != INF){
if (price[cities - 1].first > price[cities - 1].second)
printf("%lld", price[cities - 1].second);
else
printf("%lld", price[cities - 1].first);
}
else
printf("%lld", price[cities - 1].first);
}
else
printf("%lld", price[cities - 1].second);
return 0;
}