#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
using namespace std;
ifstream in ("bellmanford.in");
ofstream out ("bellmanford.out");
const int NR = 50005 ;
const int oo = 50000005 ;
vector < pair < int , pair < int , int > > > v [ NR ] ;
vector < int > d ( NR , oo ) ;
vector < int > w ( NR , oo ) ;

int viz [ NR ] , n , m ;
bool sediu [ NR ] ;
int main ()
{
 in >> n;
 for ( int i = 1 ; i <= n ; ++ i )
{
    int x; cin >> x ;
    if ( x )    sediu [ i ] = true ;
}
cin >> m ;
 while ( m -- )
 {
     int x , y , z , w ;
     in >> x >> y >> z >> w ;
     v [ x ].pb ( mp ( y , mp ( z  , w ) ) ) ;
 }

 deque < int > q ;
 q.push_back ( 1 ) ;
d [ 1 ] = 0 ;

 while ( !q.empty() )
 {
     int nod = q.front() ;
     q.pop_front() ;
     if ( nod == n )   return cout << "DA" , 0 ;
    if ( sediu [ nod ] ) w [ nod ] = 0 ;
     for( size_t i = 0 ; i < v [ nod ].size() ; ++ i )
     {
         int vecin = v [ nod ][ i ].first ;
         int dist = v [ nod ][ i ].second.first ;
         int wati = v [ nod ][ i ].second.second ;
         if ( d [ vecin ] + dist == d [ vecin ] )
            w [ vecin ] = min ( w [ vecin ] , w [ nod ] + wati ) ;
         if ( d [ vecin ] + dist < d [ vecin ] )
         {
             d [ vecin ] = d [ vecin ] + dist ;
             q.push_back ( vecin ) ;
             w [ vecin ] = w [ nod ] + wati ;
         }
     }
 }
 for ( int i = 2 ; i <= n ; ++ i )  out << d [ i ] << " " ;
 return 0 ;
}