include[HTML_REMOVED]

using namespace std;

define ll long long

define INF 0x7f7f7f7f

struct node
{
int to,w;
node(int tt,int ww):to(tt),w(ww){
}
bool operator<(const node &cmp)const
{
return w>cmp.w;
}
};
const int N=505;
const int M=1e5+5;
int dis[N];
bool vis[N];
vector[HTML_REMOVED] e[N];
int n,m;

void dij(int x)
{
fill(dis,dis+N,INF);
fill(vis,vis+N,false);
dis[1]=0;
priority_queue[HTML_REMOVED] q;
q.push(node(x,0));
while(!q.empty())
{
node now=q.top();q.pop();
if(vis[now.to]) continue;
vis[now.to]=true;
dis[now.to]=now.w;
for(int i=0;i<e[now.to].size();i++)
{
node next=e[now.to][i];
q.push(node(next.to,next.w+now.w));
}
}
}

int main()
{
cin>>n>>m;
for(int i=0;i[HTML_REMOVED]>x>>y>>l;
e[x].push_back(node(y,l));
}
dij(1);
if(dis[n]==INF) cout<<-1;
else cout<<dis[n];
return 0;
}