#include <iostream>
#include <fstream>
#include <queue>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;
#define maxn 50005
const int inf=2000000001;
queue <int> q;
vector <pair<int,int> > muchii[maxn];
bool inq[maxn];
int dmin[maxn];
int n,m,i,a,b,c,now,to,dto;
int main(void)
{
    FILE * f;
    f=fopen("djikstra.in","r");
    ofstream g("djikstra.out");
    fscanf(f,"%d%d",&n,&m);
    for (i=1;i<=m;i++)
    {
        fscanf(f,"%d%d%d",&a,&b,&c);
        muchii[a].push_back(make_pair(b,c));
    }
    for (i=0;i<=50000;i++)
    {
        dmin[i]=2000000000;
        inq[i]=false;
    }
    dmin[1]=0;
    q.push(1);
    while (!q.empty())
    {
        now=q.front();
        q.pop();
        inq[now]=false;
        for (i=0;i<muchii[now].size();i++)
        {
            to=muchii[now][i].first;
            dto=muchii[now][i].second;
            if (dmin[now]+dto<dmin[to])
            {
                dmin[to]=dmin[now]+dto;
                if (!inq[to])
                {
                    q.push(to);
                    inq[to]=true;
                }
            }
        }
    }
    for (i=2;i<=n;i++)
        g<<dmin[i]<<' ';
    g.close();
    return 0;
}