#include <fstream>
#include <vector>
#include <queue>
using namespace std;

const int N=50001,inf=1<<30;
int dist[N],n;
bool use[N];
class cmp
{
    public:
    bool operator()(const int &a,const int &b)
    {
        return dist[a]<dist[b];
    }
};
struct Muchie
{
    int y,c;
};
priority_queue<int,vector<int>,cmp> Q;
vector<Muchie> a[N];

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

void dijkstra(int x)
{
    int y,c;
    for (int i=1;i<=n;i++)
        dist[i]=inf;
    dist[x]=0;
    Q.push(x);
    while (!Q.empty())
    {
        x=Q.top();Q.pop();
        if (use[x])
            continue;
        use[x]=true;
        for (vector<Muchie>::iterator i=a[x].begin();i!=a[x].end();i++)
        {
            y=(*i).y;c=(*i).c;
            if (dist[x]+c<dist[y])
            {
                dist[y]=dist[x]+c;
                Q.push(y);
            }
        }
    }
}

int main()
{
    int m,x,y,c;
    in>>n>>m;
    while (m--)
    {
        in>>x>>y>>c;
        a[x].push_back((Muchie){y,c});
    }
    dijkstra(1);
    for (int i=2;i<=n;i++)
        out<<(dist[i]!=inf ? dist[i] : 0)<<" ";
    out<<"\n";
    return 0;
}