#include <fstream>
#include <vector>
#include <queue>
#define NMAX 50002
#define INF 1e9
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
int n,m;
struct varf {int x,c;};
vector<varf> G[NMAX];

int cmin[NMAX];
int uz[NMAX];
int pre[NMAX];

void dijkstra(int start);
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> q; //doar ca .first pun costul si .second varful

void afisare();
int main()
{
    int i,a,b,cost;
    fin>>n>>m;
    for(i=1; i<=m; i++)
        {
         fin>>a>>b>>cost;
         G[a].push_back({b,cost});
        }
    dijkstra(1);
    afisare();
    return 0;
}

void dijkstra(int start)
{
    int i,j,vecin,cost,vfmin,minim;
    //initializare cmin si pre
    for(i=1; i<=n; i++)
        {
         cmin[i]=INF;
         pre[i]=start;
        }
    cmin[start]=0;
    pre[start]=0;
    q.push({0,start});

    while(!q.empty())
    {
        minim=q.top().first;
        vfmin=q.top().second;
        q.pop();
        if(uz[vfmin]) continue;
        //il marchez pe vfmin ca selectat
        uz[vfmin]=1;
        //vad daca pot face update uri
        for(i=0; i<G[vfmin].size(); i++)
            {
             vecin=G[vfmin][i].x;
             cost=G[vfmin][i].c;
             if(!uz[vecin] && cmin[vecin]>cmin[vfmin]+cost)
                {
                 cmin[vecin]=cmin[vfmin]+cost;
                 pre[vecin]=vfmin;
                 q.push({cmin[vecin],vecin});
                }
            }
    }
}

void afisare()
{
    int i;
    for(i=2; i<=n; i++)
        if(cmin[i]==INF)
            fout<<0<<' ';
            else fout<<cmin[i]<<' ';
}