#include<bits/stdc++.h>
#define x first
#define y second
#define pb push_back
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
const int DN=50005;
int n,m,f,g,cost;
int dist[DN];
//int r[DN][DN];
vector<pair<int,int> >v[DN];
set<pair<int,int> >s;
void dij(int nod)
{
    for(int i=1;i<=n;i++)
        dist[i]=1e9;
    dist[nod]=0;
    s.insert({0,nod});
    while(!s.empty())
    {
        pair<int,int> z=*s.begin();
        s.erase(s.begin());
        nod=z.y;
        for(auto i:v[nod])
            if(dist[nod]+i.y<dist[i.x])
            {
                if(dist[i.x]!=1e9)
                    s.erase(s.find({dist[i.x],i.x}));
                dist[i.x]=dist[nod]+i.y;
                s.insert({dist[i.x],i.x});
            }
    }
}
int main()
{
    cout<<"introduceti numarul de noduri ";
    fin>>n;
    cout<<"introduceti numarul de muchii ";
    fin>>m;
    for(int i=1;i<=m;i++)
    {
        fin>>f>>g>>cost;
        v[f].pb({g,cost});
    }
    dij(1);
    for(int i=2;i<=n;i++)
        if(dist[i]==1e9)
            dist[i]=0;
    for(int i=2;i<=n;i++)
        fout<<dist[i]<<' ';
    /*for(int i=1;i<=n;i++)
    {
        dij(i);
        for(int j=1;j<=n;j++)
            r[i][j]=dist[j];
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
            cout<<r[i][j]<<' ';
        cout<<'\n';
    }*/
}