#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
 
const int N=1e6;
 
int d()
{
    int ret;
    scanf("%d", &ret);
    return ret;
}
long long lld()
{
    long long ret;
    scanf("%lld", &ret);
    return ret;
}
int n,m,OO = 0x3f3f3f3f;
vector<pair<int,int>>adj[N];
int dis[N];
int parent[N];
void dijkstra(int src){
    memset(dis,OO,sizeof dis);
    dis[src]=0;
    priority_queue<pair<int ,int>>q;
    q.push({0,src});
    parent[0]=0;
    while(!q.empty()){
        int uc=-q.top().first;
        int u=q.top().second;
        q.pop();
        if(uc!=dis[u])  continue;
        for(pair<int,int> p : adj[u]){
            int c=p.first;
            int v=p.second;
            if(dis[v]> dis[u]+c){
                dis[v]=dis[u]+c;
                q.push({-dis[v],v});
                parent[v]=u;
            }
 
        }
 
    }
}
int main()
{
    n=d(),m=d();
    for(int i=0; i<m; i++)
    {
        int u=d(),v=d(),c=d();
        u--;
        v--;
        adj[u].push_back({c,v});
        adj[v].push_back({c,u});
    }
    dijkstra(0);
    for(int i=0;i<n;i++){
        cout<<dis[i]<<" ";
    }
    puts("");
    for(int i=0;i<n;i++) {
        cout<<i+1<<" "<<parent[i]+1<<endl;
    }
}
 

I2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKdHlwZWRlZiBsb25nIGxvbmcgbGw7Cgpjb25zdCBpbnQgTj0xZTY7CgppbnQgZCgpCnsKICAgIGludCByZXQ7CiAgICBzY2FuZigiJWQiLCAmcmV0KTsKICAgIHJldHVybiByZXQ7Cn0KbG9uZyBsb25nIGxsZCgpCnsKICAgIGxvbmcgbG9uZyByZXQ7CiAgICBzY2FuZigiJWxsZCIsICZyZXQpOwogICAgcmV0dXJuIHJldDsKfQppbnQgbixtLE9PID0gMHgzZjNmM2YzZjsKdmVjdG9yPHBhaXI8aW50LGludD4+YWRqW05dOwppbnQgZGlzW05dOwppbnQgcGFyZW50W05dOwp2b2lkIGRpamtzdHJhKGludCBzcmMpewogICAgbWVtc2V0KGRpcyxPTyxzaXplb2YgZGlzKTsKICAgIGRpc1tzcmNdPTA7CiAgICBwcmlvcml0eV9xdWV1ZTxwYWlyPGludCAsaW50Pj5xOwogICAgcS5wdXNoKHswLHNyY30pOwogICAgcGFyZW50WzBdPTA7CiAgICB3aGlsZSghcS5lbXB0eSgpKXsKICAgICAgICBpbnQgdWM9LXEudG9wKCkuZmlyc3Q7CiAgICAgICAgaW50IHU9cS50b3AoKS5zZWNvbmQ7CiAgICAgICAgcS5wb3AoKTsKICAgICAgICBpZih1YyE9ZGlzW3VdKSAgY29udGludWU7CiAgICAgICAgZm9yKHBhaXI8aW50LGludD4gcCA6IGFkalt1XSl7CiAgICAgICAgICAgIGludCBjPXAuZmlyc3Q7CiAgICAgICAgICAgIGludCB2PXAuc2Vjb25kOwogICAgICAgICAgICBpZihkaXNbdl0+IGRpc1t1XStjKXsKICAgICAgICAgICAgICAgIGRpc1t2XT1kaXNbdV0rYzsKICAgICAgICAgICAgICAgIHEucHVzaCh7LWRpc1t2XSx2fSk7CiAgICAgICAgICAgICAgICBwYXJlbnRbdl09dTsKICAgICAgICAgICAgfQoKICAgICAgICB9CgogICAgfQp9CmludCBtYWluKCkKewogICAgbj1kKCksbT1kKCk7CiAgICBmb3IoaW50IGk9MDsgaTxtOyBpKyspCiAgICB7CiAgICAgICAgaW50IHU9ZCgpLHY9ZCgpLGM9ZCgpOwogICAgICAgIHUtLTsKICAgICAgICB2LS07CiAgICAgICAgYWRqW3VdLnB1c2hfYmFjayh7Yyx2fSk7CiAgICAgICAgYWRqW3ZdLnB1c2hfYmFjayh7Yyx1fSk7CiAgICB9CiAgICBkaWprc3RyYSgwKTsKICAgIGZvcihpbnQgaT0wO2k8bjtpKyspewogICAgICAgIGNvdXQ8PGRpc1tpXTw8IiAiOwogICAgfQogICAgcHV0cygiIik7CiAgICBmb3IoaW50IGk9MDtpPG47aSsrKSB7CiAgICAgICAgY291dDw8aSsxPDwiICI8PHBhcmVudFtpXSsxPDxlbmRsOwogICAgfQp9Cg==

NSA2CjEgMiAyCjIgNSA1CjIgMyA0CjEgNCAxCjQgMyAzCjMgNSAxCg==

5 6
1 2 2
2 5 5
2 3 4
1 4 1
4 3 3
3 5 1