#include<bits/stdc++.h>
using namespace std;
long long n , m , dp [1003][1003];
vector < int > gr [200005];
map < pair < int , int > , long long > col , pri , sumcol;
int main ()
{
cin >> n >> m;
for ( int i = 0 ; i < m ; i ++ )
{
int x , y;
cin >> x >> y;
gr [x] . push_back ( y );
gr [y] . push_back ( x );
cin >> col [ { x , y } ] >> pri [ { x , y } ];
col [ { y , x } ] = col [ { x , y } ];
pri [ { y , x } ] = pri [ { x , y } ];
sumcol [ { x , col [ { x , y } ] } ] += pri [ { x , y } ];
sumcol [ { y , col [ { x , y } ] } ] += pri [ { x , y } ];
}
for ( int i = 1 ; i <= n ; i ++ )
{
for ( int j = 0 ; j <= n ; j ++ ) dp [i][j] = 1e16;
}
dp [1][0] = 0;
priority_queue < pair < long long , pair < int , int > > > q;
q . push ( { 0 , { 1 , 0 } } );
long long ans = 1e16;
while ( q . size () )
{
pair < long long , pair < int , int > > p = q . top ();
q . pop ();
int x = p . second . first , last = p . second . second;
if ( x == n ) ans = min ( ans , dp [x][last] );
for ( auto u : gr [x] )
{
long long sum = sumcol [ { x , col [ { x , u } ] } ];
sum -= pri [ { x , u } ];
if ( last && col [ { x , last } ] == col [ { x , u } ] ) sum -= pri [ { x , last } ];
if ( dp [x][last] + sum < dp [u][0] )
{
dp [u][0] = dp [x][last] + sum;
q . push ( { - dp [u][0] , { u , 0 } } );
}
if ( dp [x][last] + pri [ { x , u } ] < dp [u][x] )
{
dp [u][x] = dp [x][last] + pri [ { x , u } ];
q . push ( { - dp [u][x] , { u , x } } );
}
}
}
if ( ans == 1e16 ) cout << -1;
else cout << ans;
}
