#include <iostream>
#include <vector>
#include <queue>
#include <limits>

using namespace std;

typedef pair<int, int> PII;

vector<int> dijkstra(int n, const vector<vector<PII>>& graph, int start) {
    vector<int> dist(n + 1, numeric_limits<int>::max());
    dist[start] = 0;
    priority_queue<PII, vector<PII>, greater<PII>> pq;
    pq.push({ 0, start });

    while (!pq.empty()) {
        int current_dist = pq.top().first;
        int u = pq.top().second;
        pq.pop();

        if (current_dist > dist[u])
            continue;

        for (const auto& edge : graph[u]) {
            int v = edge.first;
            int weight = edge.second;
            int distance = current_dist + weight;

            if (distance < dist[v]) {
                dist[v] = distance;
                pq.push({ distance, v });
            }
        }
    }

    return dist;
}

int main() {
    int n = 6, m = 4;
    vector<vector<PII>> graph(n + 1);

    vector<tuple<int, int, int>> edges = { { 2, 4, 4 }, { 4, 2, 2 }, { 6, 2, 2 }, { 6, 1, 2 } };

    for (const auto& edge : edges) {
        int u, v, w;
        tie(u, v, w) = edge;
        graph[u].emplace_back(v, w);
        graph[v].emplace_back(u, w);  // 因为是双向边
    }

    int start = 1;
    vector<int> distances = dijkstra(n, graph, start);

    for (int i = 1; i <= n; ++i) {
        cout << distances[i] << " ";
    }

    return 0;
}

/sandbox/1/a.cpp: In function 'int main()':
/sandbox/1/a.cpp:47:5: error: could not convert '{{2, 4, 4}, {4, 2, 2}, {6, 2, 2}, {6, 1, 2}}' from '<brace-enclosed initializer list>' to 'std::vector<std::tuple<int, int, int> >'
   47 |     };
      |     ^
      |     |
      |     <brace-enclosed initializer list>
/sandbox/1/a.cpp:51:9: error: 'tie' was not declared in this scope
   51 |         tie(u, v, w) = edge;
      |         ^~~
/sandbox/1/a.cpp:5:1: note: 'std::tie' is defined in header '<tuple>'; did you forget to '#include <tuple>'?
    4 | #include <limits>
  +++ |+#include <tuple>
    5 | 
In file included from /usr/include/c++/10/bits/stl_algobase.h:67,
                 from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 from /usr/include/c++/10/ostream:38,
                 from /usr/include/c++/10/iostream:39,
                 from /sandbox/1/a.cpp:1:
/usr/include/c++/10/bits/stl_iterator.h: In instantiation of '__gnu_cxx::__normal_iterator<_Iterator, _Container>& __gnu_cxx::__normal_iterator<_Iterator, _Container>::operator++() [with _Iterator = std::tuple<int, int, int>*; _Container = std::vector<std::tuple<int, int, int> >]':
/sandbox/1/a.cpp:49:29:   required from here
/usr/include/c++/10/bits/stl_iterator.h:980:4: error: cannot increment a pointer to incomplete type 'std::tuple<int, int, int>'
  980 |  ++_M_current;
      |    ^~~~~~~~~~
In file included from /usr/include/c++/10/vector:67,
                 from /sandbox/1/a.cpp:2:
/usr/include/c++/10/bits/stl_vector.h: In instantiation of 'std::_Vector_base<_Tp, _Alloc>::~_Vector_base() [with _Tp = std::tuple<int, int, int>; _Alloc = std::allocator<std::tuple<int, int, int> >]':
/usr/include/c++/10/bits/stl_vector.h:683:7:   required from 'std::vector<_Tp, _Alloc>::~vector() [with _Tp = std::tuple<int, int, int>; _Alloc = std::allocator<std::tuple<int, int, int> >]'
/sandbox/1/a.cpp:47:5:   required from here
/usr/include/c++/10/bits/stl_vector.h:336:35: error: invalid use of incomplete type 'class std::tuple<int, int, int>'
  336 |         _M_impl._M_end_of_storage - _M_impl._M_start);
      |         ~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/10/bits/move.h:57,
                 from /usr/include/c++/10/bits/nested_exception.h:40,
                 from /usr/include/c++/10/exception:148,
                 from /usr/include/c++/10/ios:39,
                 from /usr/include/c++/10/ostream:38,
                 from /usr/include/c++/10/iostream:39,
                 from /sandbox/1/a.cpp:1:
/usr/include/c++/10/type_traits:2631:11: note: declaration of 'class std::tuple<int, int, int>'
 2631 |     class tuple;
      |           ^~~~~
/usr/include/c++/10/type_traits: In instantiation of 'struct std::is_destructible<std::tuple<int, int, int> >':
/usr/include/c++/10/bits/stl_construct.h:177:51:   required from 'void std::_Destroy(_ForwardIterator, _ForwardIterator) [with _ForwardIterator = std::tuple<int, int, int>*]'
/usr/include/c++/10/bits/alloc_traits.h:738:15:   required from 'void std::_Destroy(_ForwardIterator, _ForwardIterator, std::allocator<_T2>&) [with _ForwardIterator = std::tuple<int, int, int>*; _Tp = std::tuple<int, int, int>]'
/usr/include/c++/10/bits/stl_vector.h:680:15:   required from 'std::vector<_Tp, _Alloc>::~vector() [with _Tp = std::tuple<int, int, int>; _Alloc = std::allocator<std::tuple<int, int, int> >]'
/sandbox/1/a.cpp:47:5:   required from here
/usr/include/c++/10/type_traits:844:52: error: static assertion failed: template argument must be a complete class or an unbounded array
  844 |       static_assert(std::__is_complete_or_unbounded(__type_identity<_Tp>{}),
      |                     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/10/bits/alloc_traits.h:33,
                 from /usr/include/c++/10/ext/alloc_traits.h:34,
                 from /usr/include/c++/10/bits/basic_string.h:40,
                 from /usr/include/c++/10/string:55,
                 from /usr/include/c++/10/bits/locale_classes.h:40,
                 from /usr/include/c++/10/bits/ios_base.h:41,
                 from /usr/include/c++/10/ios:42,
                 from /usr/include/c++/10/ostream:38,
                 from /usr/include/c++/10/iostream:39,
                 from /sandbox/1/a.cpp:1:
/usr/include/c++/10/bits/stl_construct.h: In instantiation of 'void std::_Destroy(_ForwardIterator, _ForwardIterator) [with _ForwardIterator = std::tuple<int, int, int>*]':
/usr/include/c++/10/bits/alloc_traits.h:738:15:   required from 'void std::_Destroy(_ForwardIterator, _ForwardIterator, std::allocator<_T2>&) [with _ForwardIterator = std::tuple<int, int, int>*; _Tp = std::tuple<int, int, int>]'
/usr/include/c++/10/bits/stl_vector.h:680:15:   required from 'std::vector<_Tp, _Alloc>::~vector() [with _Tp = std::tuple<int, int, int>; _Alloc = std::allocator<std::tuple<int, int, int> >]'
/sandbox/1/a.cpp:47:5:   required from here
/usr/include/c++/10/bits/stl_construct.h:177:51: error: static assertion failed: value type is destructible
  177 |       static_assert(is_destructible<_Value_type>::value,
      |                                                   ^~~~~
/usr/include/c++/10/bits/stl_construct.h:184:25: error: invalid use of incomplete type 'std::iterator_traits<std::tuple<int, int, int>*>::value_type' {aka 'class std::tuple<int, int, int>'}
  184 |       std::_Destroy_aux<__has_trivial_destructor(_Value_type)>::
      |                         ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/10/bits/move.h:57,
                 from /usr/include/c++/10/bits/nested_exception.h:40,
                 from /usr/include/c++/10/exception:148,
                 from /usr/include/c++/10/ios:39,
                 from /usr/include/c++/10/ostream:38,
                 from /usr/include/c++/10/iostream:39,
                 from /sandbox/1/a.cpp:1:
/usr/include/c++/10/type_traits:2631:11: note: declaration of 'std::iterator_traits<std::tuple<int, int, int>*>::value_type' {aka 'class std::tuple<int, int, int>'}
 2631 |     class tuple;
      |           ^~~~~
In file included from /usr/include/x86_64-linux-gnu/c++/10/x32/bits/c++allocator.h:33,
                 from /usr/include/c++/10/bits/allocator.h:46,
                 from /usr/include/c++/10/string:41,
                 from /usr/include/c++/10/bits/locale_classes.h:40,
                 from /usr/include/c++/10/bits/ios_base.h:41,
                 from /usr/include/c++/10/ios:42,
                 from /usr/include/c++/10/ostream:38,
                 from /usr/include/c++/10/iostream:39,
                 from /sandbox/1/a.cpp:1:
/usr/include/c++/10/ext/new_allocator.h: In instantiation of 'void __gnu_cxx::new_allocator<_Tp>::deallocate(_Tp*, __gnu_cxx::new_allocator<_Tp>::size_type) [with _Tp = std::tuple<int, int, int>; __gnu_cxx::new_allocator<_Tp>::size_type = unsigned int]':
/usr/include/c++/10/bits/alloc_traits.h:492:23:   required from 'static void std::allocator_traits<std::allocator<_CharT> >::deallocate(std::allocator_traits<std::allocator<_CharT> >::allocator_type&, std::allocator_traits<std::allocator<_CharT> >::pointer, std::allocator_traits<std::allocator<_CharT> >::size_type) [with _Tp = std::tuple<int, int, int>; std::allocator_traits<std::allocator<_CharT> >::allocator_type = std::allocator<std::tuple<int, int, int> >; std::allocator_traits<std::allocator<_CharT> >::pointer = std::tuple<int, int, int>*; std::allocator_traits<std::allocator<_CharT> >::size_type = unsigned int]'
/usr/include/c++/10/bits/stl_vector.h:354:19:   required from 'void std::_Vector_base<_Tp, _Alloc>::_M_deallocate(std::_Vector_base<_Tp, _Alloc>::pointer, std::size_t) [with _Tp = std::tuple<int, int, int>; _Alloc = std::allocator<std::tuple<int, int, int> >; std::_Vector_base<_Tp, _Alloc>::pointer = std::tuple<int, int, int>*; std::size_t = unsigned int]'
/usr/include/c++/10/bits/stl_vector.h:335:2:   required from 'std::_Vector_base<_Tp, _Alloc>::~_Vector_base() [with _Tp = std::tuple<int, int, int>; _Alloc = std::allocator<std::tuple<int, int, int> >]'
/usr/include/c++/10/bits/stl_vector.h:683:7:   required from 'std::vector<_Tp, _Alloc>::~vector() [with _Tp = std::tuple<int, int, int>; _Alloc = std::allocator<std::tuple<int, int, int> >]'
/sandbox/1/a.cpp:47:5:   required from here
/usr/include/c++/10/ext/new_allocator.h:123:6: error: invalid application of '__alignof__' to incomplete type 'std::tuple<int, int, int>'
  123 |  if (alignof(_Tp) > __STDCPP_DEFAULT_NEW_ALIGNMENT__)
      |      ^~~~~~~~~~~~
/usr/include/c++/10/ext/new_allocator.h:127:16: error: invalid application of 'sizeof' to incomplete type 'std::tuple<int, int, int>'
  127 |          __t * sizeof(_Tp),
      |                ^~~~~~~~~~~
/usr/include/c++/10/ext/new_allocator.h:129:27: error: invalid application of '__alignof__' to incomplete type 'std::tuple<int, int, int>'
  129 |          std::align_val_t(alignof(_Tp)));
      |                           ^~~~~~~~~~~~
/usr/include/c++/10/ext/new_allocator.h:135:14: error: invalid application of 'sizeof' to incomplete type 'std::tuple<int, int, int>'
  135 |      , __t * sizeof(_Tp)
      |              ^~~~~~~~~~~