#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#define inf 1<<30
#define NMax 50005
using namespace std;

typedef vector<pair<int,int> > VP;
VP vc[NMax];

struct comp {
    bool operator () (pair<int,int> i, pair<int,int> j)
    {
        return i.second<j.second;
    }
};
priority_queue<pair<int,int>,VP,comp> Q;

int d[NMax];

int main ()
{
    int n,m,i,a,b,c,nod;
    pair<int,int> crt;
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    scanf("%d%d",&n,&m);
    for (i=1; i<=m; i++)
    {
        scanf("%d%d%d",&a,&b,&c);
        vc[a].push_back(make_pair(b,c));
    }
    for (i=1; i<=n; i++)
        d[i]=inf;
    Q.push(make_pair(1,0));
    d[1]=0;
    while (!Q.empty())
    {
        crt=Q.top(), nod=crt.first;
        Q.pop();
        for (i=0; i<vc[nod].size(); i++)
            if (d[vc[nod][i].first]>d[nod]+vc[nod][i].second)
            {
                d[vc[nod][i].first]=d[nod]+vc[nod][i].second;
                Q.push(make_pair(vc[nod][i].first,d[vc[nod][i].first]));
            }
    }
    for (i=2; i<=n; i++)
        printf("%d ",(d[i]!=inf) ? d[i] : 0);
    return 0;
}