#include <fstream>
#include <iostream>
#include <bitset>
#include <vector>

using namespace std;
int n, m;
const int  INF=1e9;
ifstream in("dijkstra.in");
ofstream out("dijkstra.out");
vector <pair <int, int> >lista[50002];
int d[50001];
int uzat[50001];
int tati[50001];
int main()
{
    in>>n>>m;
    int x, y, cost;
    while(in>>x>>y>>cost)
    {
        lista[x].push_back({y, cost});
        cout<<x<<" "<<y<<" "<<cost<<endl;
    }
    d[1]=0;
    for(int i=2; i<=n; i++)
    {
        d[i]=INF;
    }
    tati[1]=0;
    d[1]=0;
    uzat[1]=1;
    for(int i=0;i<lista[1].size();i++)
    {
        d[lista[1][i].first]=lista[1][i].second;

    }

    for(int i=1; i<=n; i++)
    {
        int costmin=INF;
        int vfmin=0;
        for(int j=1; j<=n; j++)
        {
            if(costmin>d[j] and uzat[j]==0)
            {
                costmin=d[j];
                vfmin=j;
            }
        }
        d[vfmin]=costmin;
        uzat[vfmin]=1;
        cout<<vfmin<<" ";
        for(int i=0;i<lista[vfmin].size();i++)
        {
            cout<<(d[lista[vfmin][i].first]>costmin+lista[vfmin][i].second)<<" "<<d[lista[vfmin][i].first]<<" "<<costmin+lista[vfmin][i].second<<endl;
            if(!uzat[lista[vfmin][i].first] and d[lista[vfmin][i].first]>costmin+lista[vfmin][i].second)
            {
                cout<<"BA";
                d[lista[vfmin][i].first]=costmin+lista[vfmin][i].second;
                tati[lista[vfmin][i].first]=vfmin;
            }
        }
    }
    for(int i=2; i<=n; i++)
    {
        if(d[i]!=INF)
        {out<<d[i]<<" ";
        }
        else
        {
            out<<"0"<<" ";
        }
    }
    return 0;
}