#include <cstdio>
#include <iostream>
#include <queue>
#define nmax 50004
using namespace std;
struct nd
{
    int node,dist;
};
int n,m1;
vector<nd> m[nmax];
int d[nmax];

class mycomparison
{
public:
    bool operator () ( const int &lh,const int &rh) const
    {
        return d[lh]>d[rh];
    }
};
priority_queue<int,vector<int>,mycomparison> q;

inline void dij()
{
    int i;
    for(i=1;i<=n;i++) d[i]=0x7fffffff;
    d[1]=0;
    int crt;
    q.push(1);

    while(!q.empty())
    {
        crt=q.top(); q.pop();
        for(i=0;i<m[crt].size();i++)
            if( d[m[crt][i].node] > d[crt]+m[crt][i].dist)
            {
                q.push(m[crt][i].node);
                d[m[crt][i].node]=d[crt]+m[crt][i].dist;
            }
    }
}

int main()
{
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    cin>>n>>m1;
    int n1;
    nd nodul;
    for(;m1;m1--)
    {
        cin>>n1>>nodul.node>>nodul.dist;
        m[n1].push_back(nodul);
    }
    dij();
    for(int i=2;i<=n;i++) cout<<d[i]<<' ';
    fclose(stdin);
    fclose(stdout);
    return 0;
}