#include 
#include 
#include 
#include 
#include 
using namespace  std;
struct node {
    int index,shortest_path,snow;

    node(int i,int p,int s){
        index = i;
        shortest_path = p;
        snow = s;
    }

    bool operator < (const node &tmp)const{
        return shortest_path > tmp.shortest_path;
    }
};
struct broevi {
    int b,c,d;

    broevi(int _b,int _c, int _d){
        b = _b;
        c = _c;
        d = _d;
    }
};
int main() {
    int n, m;
    cin >> n >> m;
    vector graph [n + 5];
    for (int i = 0; i < m; i++) {
        int a,b,c,d;
        cin >> a >> b >> c >> d;
        graph[a].push_back(broevi(b,c,d));
        graph[b].push_back(broevi(a,c,d));
    }
   priority_queue pq;
   pq.push(node(1,0,1));

   vector visited (n+1, false);
   vector distance ( n+1,2e9);

   while (!pq.empty()){
       node current = pq.top();
       pq.pop();

       visited[current.index] = true;
       if(current.index == n && current.snow == 1){
           cout << current.shortest_path << endl;
           cout << "DA" << endl;
           break;
       }
       if(current.index == n && current.snow == 0){
           cout << current.shortest_path << endl;
           cout << "NE" << endl;
           break;
       }
       for (int i = 0; i