#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)
{
    use[nod]=1;
    int j,cost;
    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 Min=oo;
    for(int i=1;i<=n;i++)
    {
            if(use[i]==0 && Min>D[i])
            {
                Min=D[i];
                j=i;
            }
    }
    dijsktra(j);
}
int main()
{
read();
for(int i=1;i<n;i++)
    D[i]=oo;
    D[1]=0;
dijsktra(1);
for(int i=2;i<n;i++)
    fout<<"distanta pana la nodul "<<i<<" este "<<D[i]<<endl;
return 0;
}