#include 
#include
#include
using namespace std;
struct node
{
    int idx;
    int distance;
    int snow;
    node(){}
    node(int _idx, int _distance, int _snow)
    {
        idx=_idx;
        distance=_distance;
        snow=_snow;
    }
    bool operator < (const node &tmp) const{
        return distance > tmp.distance;
    }
};
int main()
{
    int n,m;
    cin>>n>>m;
    vectorv[n+1];
    for(int i=0;i>a>>b>>c>>d;
       v[a].push_back(node(b,c,d));
       v[b].push_back(node(a,c,d));
    }
    priority_queuepq;
    pq.push(node(1,0,1));
    bool visited[n+1][2];
    for(int i=0;i