#include <cstdio>
#include <vector>
#include <queue>
#define NMAX 50005
#define INF 1000000
using namespace std;
FILE* fin=fopen("dijkstra.in","r");
FILE* fout=fopen("dijkstra.out","w");
void citire();
void rezolvare();
void scriere();
int n,m;
vector < pair<int,int> > G[NMAX];
queue <int> q;
int dmin[NMAX];
bool uz[NMAX];
int main()
{
    citire();
    rezolvare();
    scriere();
    return 0;
}
void citire()
{
    int a,b,c;
    fscanf(fin,"%d %d",&n,&m);
    for (int i=0; i<m; i++)
    {
        fscanf(fin,"%d %d %d",&a,&b,&c);
        G[a].push_back(make_pair(b,c));
    }
}
void rezolvare()
{
    int i,nod;
    for (i=1; i<=n; i++) {uz[i]=0; dmin[i]=INF;}
    q.push(1); uz[1]=1; dmin[1]=0;
    while (!q.empty())
    {
        nod=q.front(); q.pop(); uz[nod]=0;
        for (i=0; i<G[nod].size(); i++)
        {
            if (dmin[G[nod][i].first]>dmin[nod]+G[nod][i].second)
            {
                dmin[G[nod][i].first]=dmin[nod]+G[nod][i].second;
                if (!uz[G[nod][i].first])
                {
                    q.push(G[nod][i].first);
                    uz[G[nod][i].first]=1;
                }
            }
        }
    }
}
void scriere()
{
    for (int i=2; i<=n; i++) fprintf(fout,"%d ",dmin[i]);
    fprintf(fout,"\n");
}