/*
*/
#include <iostream>
#include <fstream>
#include <vector>
#define oo 2000000000
#define NMax 50000
using namespace std;
ifstream fin("dijsktra.in");
ofstream fout("dijsktra.out");
vector <pair <int,int> > v[100005];
int n,m;
bool use[NMax];
int D[NMax];
void read()
{
    int x,y,G;
    fin>>n>>m;
    for(int i=0;i<m;i++)
    {
        fin>>x>>y>>G;
        v[x].push_back(make_pair(y,G));
    }
}
void dijsktra()
{

    int nod,cost,vecin;
    for(int i=1;i<=n;i++){
            int Min=oo;
    for(int j=1;j<=n;i++)
    {
            if(use[i]==0 && Min>D[i])
            {
                Min=D[j];
                nod=j;
            }
    }
    use[nod]=1;
    for(int i=0;i<v[nod].size();i++)
        {
            int vecin=v[nod][i].first;
            cost=v[nod][i].second;
            D[vecin]=min(D[vecin],D[nod]+cost);
        }

    }
}
int main()
{
read();
for(int i=1;i<n;i++)
    D[i]=oo;
    D[1]=0;
dijsktra();
for(int i=2;i<n;i++)
    fout<<"distanta pana la nodul "<<i<<" este "<<D[i]<<endl;
return 0;
}