#include 
#include 
#include 
#include 
using namespace std;
const int maxn=1e5;
vector, int>> graph[maxn];

struct node {
 int idx,dali_ima_sneg,shortest_distance;
 node(){}
 node(int _idx,int _dali_ima_sneg, int _shortest_distance){
    idx = _idx;
    dali_ima_sneg = _dali_ima_sneg;
    shortest_distance = _shortest_distance;
 }
 bool operator < (const node & tmp) const {
   return shortest_distance > tmp.shortest_distance;
 }
};

int main()
{
    int n,m;
    cin>>n>>m;
    for(int i = 0;i>a>>b>>c>>d;
        graph[a].push_back(make_pair(make_pair(b,c),d));
        graph[b].push_back(make_pair(make_pair(a,c),d));
    }

    priority_queuepq;
    pq.push(node(1,1,0));
    int shortest = 2e9;
    string res = "";
    bool visited[maxn][2];

    for(int i = 0;i