#include <iostream>
#include <vector>
#include <queue>
#include <deque>
#include <limits>
using namespace std;

const int INF = numeric_limits<int>::max()>>1;

typedef pair<int,int> PII;


void read_graph_dijkstra(vector<vector<int>> &);


int main(){
    vector< vector<int> > graph_dist;
    read_graph_dijkstra(graph_dist);


    cout<<"JUST TESTING MEMORY LIMIT... :))"<<'\n';

}


void read_graph_dijkstra(vector< vector<int> > &dist){
    int n,m; cin>>n>>m;

    dist.resize(n+1,vector<int>(n+1,INF));

    vector< vector<PII> > Adj(n+1);
    for(int i=0;i<m;++i){
        int t,u,v,c; cin>>t>>u>>v>>c;
        Adj[u].push_back(PII(v,c));
        if(t==2) Adj[v].push_back(PII(u,c));
    }   

    for(int st=1;st<=n;++st){
        dist[st][st]=0;
        priority_queue<PII,deque<PII>,std::greater<PII>> pq;
        pq.push(PII(0,st));
        
        while(!pq.empty()){
            int c=pq.top().first;
            int v=pq.top().second;
            pq.pop();

            if(dist[st][v]==c)
                for(auto it=Adj[v].begin();it!=Adj[v].end();++it)
                    if(dist[st][it->first] > c + it->second)
                        pq.push(PII((dist[st][it->first]=c+it->second) , it->first)); 
        }
    }
}