#include <bits/stdc++.h>
using namespace std;
#define maxn 100005
#define int long long
int n,m;
struct node{
    int x,y;
};
int dis[maxn];
bool vist[maxn];
vector<node>g[maxn];
vector<node>gg_bound[maxn];
void dj(int s){
    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>q;
    for(int i=0;i<maxn;i++)
        dis[i]=0x3f3f3f;
    dis[s]=0;
    q.push(make_pair(0,s));
    while(q.size()){
        int head=q.top().second;
        q.pop();
        if(vist[head])
            continue;
        vist[head]=true;
        for(int i = 0; i < g[head].size(); i++){
            int v = g[head][i].x;
            int w = g[head][i].y;
            if(dis[head] + w < dis[v]){
                dis[v] = dis[head] + w;
                q.push(make_pair(v,dis[v]));
            }
        }
    }
}
void djj(int s){ 
    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>qq;
    for(int i=0;i<maxn;i++)
        dis[i]=0x3f3f3f;
    dis[s]=0;
    qq.push(make_pair(0,s));
    while(qq.size()){
        int head=qq.top().second;
        qq.pop();
        if(vist[head])
            continue;
        vist[head]=true;
        for(int i = 0; i < gg_bound[head].size(); i++){
            int v = gg_bound[head][i].x;
            int w = gg_bound[head][i].y;
            if(dis[head] + w < dis[v]){
                dis[v] = dis[head] + w;
                qq.push(make_pair(v,dis[v]));
            }
        }
    }
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int i=0;i<m;i++){
        int x,y,z;
        cin>>x>>y>>z;
        g[x].push_back(node{y,z});
        gg_bound[y].push_back(node{x,z});
    }
    dj(1);
    int ans=0;
    for(int i=1;i<=n;i++){
        ans+=dis[i];
        cout<<dis[i]<<" ";
    }
    cout << endl;
    for(int i=0;i<maxn;i++)
        vist[i]=false;
    djj(n);
    for(int i=1;i<=n;i++){
        ans+=dis[i];
        cout << dis[i] << " ";
    }
    cout<<ans;
    return 0;
}