#include<iostream>
#include<unordered_map>
#include<vector>
#include<algorithm>
#include<string>
#include<math.h>
#include<map>
#include<set>
#include<string.h>
#include<iomanip>
#include<queue>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> PII;
//int mod = 998244353;


int cnt = 0, head[300005]{};
struct { int to, next, w; }edge[300005];
void addedge(int u, int v, int w)
{
	cnt++;
	edge[cnt].to = v;
	edge[cnt].w = w;
	edge[cnt].next = head[u];
	head[u] = cnt;
}

int U, V, W;
int n, m,num=1e9+1;

int vis[300005]{};
void dfs(int u,int l)
{
	vis[u] = 1;
	if (u == n)
	{
		num = min(l, num);
		return;
	}

	for (int i=head[u];i>0;i=edge[i].next)
	{
		int v = edge[i].to;
		int w = edge[i].w;
		if (vis[v] == 0)
		{
			dfs(v, l + w);
		}
		vis[v] = 0;
	}
}

int main()
{

	cin >> n >> m;
	int t = m;
	
	while (t--)
	{
		cin >> U >> V >> W;
		addedge(U, V, W);
	}

	dfs(1,0);
	cout << num;
}