#include <iostream>
#include <cstring>
#include <set>
#include <vector>
#include <fstream>

using namespace std;
const int N=50100,inf=1<<31-1;

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

int n,m,d[N];
vector <int> g[N],c[N];
set<pair<int,int> >T;

void dijkstra ()
{
    int i,j,k,val,x;
    for (i=2;i<=n;i++)
        d[i]=inf;
        T.insert (make_pair (0,1));
    while (T.size()>0)
        {
            val=(*T.begin()).first;
            x=(*T.begin()).second;
            T.erase (*T.begin());
            for (i=0;i<g[x].size();i++)
                if (d[g[x][i]]>val+c[x][i])
                    {
                        d[g[x][i]]=val+c[x][i];
                        T.insert(make_pair(d[g[x][i]],g[x][i]));
                    }
        }
}

int main()
{
    int i,a,b,v;
    in>>n>>m;
    for (i=1;i<=m;i++)
        {
            in>>a>>b>>v;
            g[a].push_back(b);
            c[a].push_back(v);
        }
        dijkstra();
    for (i=2;i<=n;i++)
        if (d[i]==inf) cout<<0<<" ";
            else out<<d[i]<<" ";
    return 0;
}