#include <fstream>
#include <vector>
#include <cstring>
#include <queue>

using namespace std;

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

#define nmax 50010
#define mp make_pair
#define inf 0x3f3f3f3f
#define foor(it,v) for(it=v.begin();it!=v.end();++it)
//#define cout g

vector < pair<int,int> > G[nmax];
vector < pair<int,int> > ::iterator it;
vector <int> dist;
priority_queue <pair<int,int> >q;

int n,m,i,a,b,c;

void dijkstra(int start)
{
    int nod;
    dist[start]=0;
    q.push(mp(0,1));
    while(!q.empty())
    {
        nod=q.top().second;
        q.pop();
        foor(it,G[nod])
        if(dist[it->first]>=dist[nod]+it->second)
        {
            dist[it->first]=dist[nod]+it->second;
            q.push(mp(-dist[it->first],it->first));
        }
    }

}

int main()
{
    f>>n>>m;
    dist.resize(n+2,inf);

    for(;m;--m)
    {
        f>>a>>b>>c;
        G[a].push_back(mp(b,c));
    }

    dijkstra(1);
    for(i=2;i<=n;++i) if(dist[i]!=inf)g<<dist[i]<<' ';
    else g<<"0 ";
}