#include <fstream>
#include <vector>
#include <queue>
#include <bitset>
#define nmax 50002
#define inf 1000000000
using namespace std;
ifstream in("dijkstra.in");
ofstream out("dijkstra.out");
class cmp{
public:
    bool operator()(pair<int,int>A,pair<int,int>B)
    {
        return A.second>B.second;
    }
};
int dist[nmax];
priority_queue <pair<int,int>, vector<pair<int,int>>,cmp> coada;
vector <pair<int,int>> g[nmax];
bitset <nmax> vizitat;
int main()
{
    int n,m,i,x,y,c;
    in>>n>>m;
    for(i=1;i<=m;i++)
    {
        in>>x>>y>>c;
        g[x].push_back(make_pair(y,c));
    }
    for(i=1;i<=n;i++)
    {
        dist[i]=inf;
    }
    dist[1]=0;
    coada.push(make_pair(1,0));
    while(!coada.empty())
    {
        int nod=coada.top().first;
        coada.pop();
        if(!vizitat[nod])
        {
            for(i=0;i<g[nod].size();i++)
            {
                x=g[nod][i].first;
                y=g[nod][i].second;
                int cs=dist[x];
                if(dist[x]>dist[nod]+y)
                {
                    dist[x]=dist[nod]+y;
                    coada.push(make_pair(x,dist[x]));
                }
            }
            vizitat[nod]=1;
        }
    }
    for(i=2;i<=n;i++)
    {
        if(dist[i]==inf)
            dist[i]=0;
        out<<dist[i]<<" ";
    }
    return 0;
}