#include <iostream>
#include <stdio.h>
#include <vector>
#include <queue>
using namespace std;
FILE *f, *g;
class compar
{
    public:
        bool operator() (pair <int,int> x, pair <int,int> y)
        {
            return(x.second > y.second);
        }

};
priority_queue <pair <int,int>, vector <pair <int,int> >,compar> q;
vector <pair <int,int> > v[50002];
bool fr[50002];
int drum[50002];
int n,m;
void read()
{   int x,y,c;
    fscanf(f,"%d %d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        fscanf(f,"%d %d %d",&x,&y,&c);
        v[x].push_back({y,c});
    }
}
void dijkstra()
{   int nod,vecin,cost,costf;
    for(int i=1;i<=n;i++)
        drum[i]=2000000000;
    q.push({1,0});
    drum[1]=0;
    while(!q.empty())
    {
        nod=q.top().first;
        q.pop();
        if(!fr[nod])
        {
            for(int i=0;i<v[nod].size();i++)
            {
                vecin=v[nod][i].first;
                cost=v[nod][i].second;
                costf=drum[nod]+cost;
                if(drum[vecin]>costf)
                {
                    drum[vecin]=costf;
                    q.push({vecin,cost});
                }
            }
        }
        fr[nod]=1;
    }
}
void write()
{
    for(int i=2;i<=n;i++)
    {
        if(drum[i]!=2000000000)
            fprintf(g,"%d ",drum[i]);
        else
            fprintf(g,"0 ");
    }
}
int main()
{
    f=fopen("dijkstra.in","r");
    g=fopen("dijkstra.out","w");
    read();
    dijkstra();
    write();
    fclose(f);
    fclose(g);
    return 0;
}